PKU 1274 The Perfect Stall
http://poj.org/problem?id=1274
n匹の牛とm個の小部屋がある。
ある牛iはSi個の小部屋a_0,a_1,...,a_(Si-1)のうちのどれかに入りたいと考えている。
希望が満たされる牛の最大数を求めろというような問題。
二部グラフ最大マッチングです。
wikipediaを見て頑張ったりしましたが、いまいちアルゴリズムが納得できていません。
蟻本のフローとかのページも自分には難しくて、理論を納得しきれていないのでなんとかしたいです。
augment pathというのがよく分からなくて困ったのですが、
http://www.cs.duke.edu/courses/fall97/cps130/lectures/lect17/node18.html
適当に検索にヒットしたこのページのアルゴリズムを実装しました。
int n,m; vector<int> G[400]; int match[400]; bool vis[400]; bool augment(int u){ vis[u]=true; rep(i,SZ(G[u])){ if(match[G[u][i]]==-1){ match[G[u][i]]=u; match[u]=G[u][i]; return true; } if(vis[match[G[u][i]]])continue; if(augment(match[G[u][i]])){ match[u]=G[u][i]; match[G[u][i]]=u; return true; } } return false; } main(){ while(cin>>n>>m){ memset(match,-1,sizeof(match)); rep(i,n+m)G[i].clear(); rep(i,n){ int nu; cin>>nu; rep(j,nu){ int t; cin>>t; --t; t+=n; G[i].pb(t); G[t].pb(i); } } int ans=0; rep(i,n){ if(match[i]!=-1)continue; memset(vis,0,sizeof(vis)); if(augment(i))++ans; } cout<<ans<<endl; } }