2部マッチング

• Quiz
  • Bipartite Matching
  • http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A
• AC
  • http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4875362#1
• 解法
  • 2部マッチングは最大フローで解ける
• その他
  • 最大フローにはatcoder libraryを用いた

#include <atcoder/maxflow>
using namespace atcoder; // 忘れがち

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll X,Y,E;
    cin>>X>>Y>>E;

    VI x(E);
    VI y(E);
    rep(i,E){
      cin>>x[i]>>y[i];
    }

    mf_graph<ll> graph(202);
    rep(i,E){
      ll a = x[i];
      ll b = y[i];
      b+=100;
      graph.add_edge(a,b,1);
    }
    
    ll start=200;
    {
      set<ll> se;
      rep(i,E) se.insert(x[i]);
      for(ll a : se){
        graph.add_edge(start, a, 1);
      }
    }
    
    ll end=201;
    {
      set<ll> se;
      rep(i,E) se.insert(y[i]+100);
      for(ll a : se){
        graph.add_edge(a,end,1);
      }
    }
    
    ll fl = graph.flow(start,end);
    p(fl);
    
    return 0;
}