kmjp's blog

競技プログラミング参加記です

TopCoder SRM 632 Div1 Medium CandyCupRunningCompetition

うーん、ひどい出来。
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);
	}
}

まとめ

辺のコストに極端に差がある場合、大きい順に流すのは定番テクらしい。