Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Bipartite Matching"
https://onlinejudge.u-aizu.ac.jp/problems/GRL_7_A
・2部マッチング
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #GRL_7_A : Bipartite Matching
/* Aizu Online Judge in C++ #GRL_7_A : Bipartite Matching https://onlinejudge.u-aizu.ac.jp/problems/GRL_7_A 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; const int s=200,t=201; int n,m,k,x,y,z=0; int c[202][202]; bool tf[202]; int f(int j){ if(j==t){ return 1; } for(int i=0;i<202;i++){ if(!tf[i] && c[j][i]>0){ tf[i]=true; int d=f(i); if(d>0){ c[j][i]=0; c[i][j]=1; return d; } } } return 0; } int main(void){ cin>>n>>m>>k; for(int i=0;i<k;i++){ cin>>x>>y; y+=100; c[s][x]=1; c[x][y]=1; c[y][t]=1; } while(f(s)){ z++; fill(tf,tf+202,0); } cout<<z<<endl; return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/