うーん、ひどい出来。
http://community.topcoder.com/stat?c=problem_statement&pm=13323
問題
N要素M辺からなるグラフが与えられる。
i番目の辺は(3^i)台の車が通行できる。
0番の点から(N-1)番の点に移動できる最大の車数を答えよ。
解法
基本的には最大フロー。ただし辺の容量が最大3^Mと大きいので、高速に計算できる多倍長整数ライブラリでないとダメ。
ここで辺の特性を活かした別解を考える。
辺のコストは3倍ずつ増えるので、i番未満の辺の容量を全部足してもi番の容量より小さい。
この事実より、以下のように処理すればよい。
- 容量の大きい順に辺を張り、その都度0→(N-1)に到達可能か調べる。
- 到達可能な場合、その辺を張ったことで到達可能になったということは、他の辺はもっと容量が大きいので、今回張った辺の容量3^iの分だけ全力でフローを流せるので、答えに3^iを加える。すると今回張った辺の容量は使い切るので、その辺は削除する。他の辺はまだまだ容量があるので残す。
- 到達不可能な場合、その辺は残す。
ll pw(int cur,int p) { static ll pw_[14][3010], mo=1000000007; if(!pw_[cur][0]) { pw_[cur][0]=1; for(int j=0;j<3000;j++) pw_[cur][j+1]=pw_[cur][j]*cur%mo; } return pw_[cur][p]; } class CandyCupRunningCompetition { public: int M; vector<int> E[2002]; int reach(int t){ int vis[2001],i; ZERO(vis); queue<int> Q; vis[0]=1; Q.push(0); while(Q.size()) { int cur=Q.front(); Q.pop(); FOR(i,E[cur].size()) { int tar=E[cur][i]; if(vis[tar]==0) vis[tar]=1,Q.push(tar); } } return vis[t]; } int findMaximum(int N, vector <int> A, vector <int> B) { M=A.size(); int i; ll ret=0; FOR(i,N) E[i].clear(); for(i=M-1;i>=0;i--) { E[A[i]].push_back(B[i]); E[B[i]].push_back(A[i]); if(reach(N-1)) { ret+=pw(3,i); E[A[i]].pop_back(); E[B[i]].pop_back(); } } return (int)(ret%1000000007); } }
まとめ
辺のコストに極端に差がある場合、大きい順に流すのは定番テクらしい。