PKU 2239 Selecting Courses
http://poj.org/problem?id=2239
ある生徒が7日間x12時間の時間割で出来るだけ多くの種類の授業を取ろうとしている。
ある種類の授業が開講される時間のリストが与えられるので、取れる種類の最大数を求めろというような問題。
二部グラフの最大マッチングになります。
さっきやったばかりですが、何も見ずにすんなり書けるようになりたいですね。
相変わらず理論が微妙に腑に落ちていないです。
vector<int>G[300]; int match[300+12*7]; bool vis[300+12*7]; 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[G[u][i]]=u; match[u]=G[u][i]; return true; } } return false; } main(){ int n; while(cin>>n){ memset(match,-1,sizeof(match)); rep(i,n){ G[i].clear(); int t; cin>>t; rep(j,t){ int a,b; cin>>a>>b; --a,--b; a=a*12+b+n; G[i].pb(a); } } int ans=0; rep(i,n){ if(match[i]!=-1)continue; memset(vis,0,sizeof(vis)); if(augment(i))++ans; } cout<<ans<<endl; } }