4130:P2P Currency Service

問題文
https://icpcarchive.ecs.baylor.edu/external/41/4130.pdf

人の名前と要らないものと欲しいもののリストが与えられる。
物々交換により欲しいものを手に入れたい。
自分が持っているいらないものが相手の欲しいものであり、かつ
自分の欲しいものが相手のいらないものだった場合にのみ交換が成立する。
また、交換は一人一回しかできない。
物々交換が成立するペアの最大値を求めよ。

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

1.それぞれの人を頂点として、縦に左側と右側に並べる。
2.スタートの頂点とゴールの頂点を用意する。
3.スタートの頂点から左側の各頂点に、右側の各頂点からゴールの頂点へそれぞれ流量1の辺を張る(一人一回しか交換できない->流量1)。
4.物々交換が成立した人同士の間に、左側から右側へ流量1の辺を張る。
5.このグラフでスタートからゴールへの最大流を求める。このグラフは二部グラフであるから、最大マッチングを求めていることになる。
6.A->BとB->Aどちらにも辺を張っているので、最後に2で割ればよい。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#define all(c) (c).begin(),(c).end()
#define INF (1<<29)
 
using namespace std;
 
struct edge{
  int to,cap,rev;
};
 
vector<edge>G[2001];
 
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});
}
 
bool used[2001];
 
int dfs(int v,int t,int 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){
      int d=dfs(e.to,t,min(e.cap,f));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}
 
int max_flow(int s,int t){
  int f=0;
  for(;;){
    fill(used,used+2001,false);
    int flow=dfs(s,t,INF);
    if(flow==0)return f;
    f+=flow;
  }
}
 
int main(void){
 
  int t,n;
  cin >> t;
  while(t--){
    for(int i=0;i<2001;i++)G[i].clear();
    cin >> n;
    vector<string>v(n),from(n),to(n),name(n);
 
    for(int i=0;i<n;i++){
      cin >> v[i] >> from[i] >> to[i];
      name[i]=v[i];
    }
 
    sort(all(name));
    name.erase(unique(all(name)),name.end());
 
    int N=name.size();
    map<string,int>q;
    for(int i=0;i<N;i++)q[name[i]]=i;
 
    /*
     0~n-1   -> 左側
     n~2*n-1 -> 右側
     2*n     -> スタート
     2*n+1   -> ゴール
    */
    for(int i=0;i<N;i++){
      add_edge(2*N,i,1);      //スタート -> 左側
      add_edge(i+N,2*N+1,1);  //右側 -> ゴール
    }
 
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(v[i]==v[j])continue;
        if(from[i]==to[j] && to[i]==from[j]){
          add_edge(q[v[i]],q[v[j]]+N,1);  //左側 -> 右側
        }
      }
    }
    cout << max_flow(2*N,2*N+1)/2 << endl;
  }  
  return 0;
}