PKU 1698 Alice's Chance
http://poj.org/problem?id=1698
何週間かを使っていくつかの映画の撮影をしなくてはならない。
ある映画は一週間のうちの決まった曜日に撮影することができ、W週以内にD日撮影する必要がある。
このとき、全ての映画の撮影を問題なくこなすことが可能かどうかを答えろというような問題。
変形二部グラフ最大マッチング的な問題。
一つの映画の何日目の撮影というノードを、組み合わせることが可能な日付に全てマッチさせることができればいい。
int matchd[2500]; int matchf[2500]; bool vis[2500]; vector<int> G[1000]; bool augment(int v){ vis[v]=true; rep(i,SZ(G[v])){ int to=G[v][i]; if(matchf[to]==-1){ matchf[to]=v; matchd[v]=to; return true; } if(!vis[matchf[to]] && augment(matchf[to])){ matchf[to]=v; matchd[v]=to; return true; } } return false; } void solve(){ int n; cin>>n; rep(i,1000)G[i].clear(); int gs=0; rep(i,n){ int we[7]; rep(j,7)cin>>we[j]; int d,w; cin>>d>>w; rep(j,d){ rep(k,w)rep(l,7)if(we[l])G[gs].pb(k*7+l); ++gs; } } memset(matchd,-1,sizeof(matchd)); memset(matchf,-1,sizeof(matchf)); rep(i,gs){ if(matchd[i]!=-1)continue; memset(vis,0,sizeof(vis)); if(!augment(i)){ cout<<"No"<<endl; return; } } cout<<"Yes"<<endl; } main(){ int T; cin>>T; while(T--)solve(); }