5874:Social Holidaying

問題文
https://icpcarchive.ecs.baylor.edu/external/58/5874.pdf

二部グラフのマッチング。

嘘解法だった。本当は一般グラフのマッチングで解くらしい。

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>

#define INF 1LL<<62
#define MAX_V 1000

using namespace std;

typedef long long ll;

struct edge{ll to,cap,rev;};

vector<edge>G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});

}

ll dfs(ll v,ll t,ll f){
  if(v==t)return f;
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    edge &e=G[v][i];
    if(!used[e.to] && e.cap>0){
      ll d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap-=d;
	G[e.to][e.rev].cap+=d;
	return d;
      }
    }
  }
  return 0;
}

ll max_flow(int s,int t){
  ll flow=0;
  for(;;){
    fill(used,used+MAX_V,false);
    ll f=dfs(s,t,INF);
    if(f==0)return flow;
    flow+=f;
  }
}

int main(void){
  int tc;
  cin >> tc;
  while(tc--){

    for(int i=0;i<MAX_V;i++)G[i].clear();

    int n,m;
    cin >> n >> m;
    vector<int>v(n);
    for(int i=0;i<n;i++)cin >> v[i];

    set<int>S;
    for(int i=0;i<m;i++){
      int a;
      cin >> a;
      S.insert(a);
    }

    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(i==j)continue;
	if(S.count(v[i]+v[j]))add_edge(i,j+n,1);
      }
    }

    for(int i=0;i<n;i++)add_edge(2*n,i,1);
    for(int i=0;i<n;i++)add_edge(i+n,2*n+1,1);
    cout << max_flow(2*n,2*n+1)/2 << endl;
  }
  return 0;
}