SRM 632 Div1 Medium CandyCupRunningCompetition

辺の容量にものすごく差がある場合の max flow を解く。
辺 i の容量は、3^i で、コストが大きい辺から greedy に使っていけばよい。(容量の小さい辺を通るフローのために容量を残しても解は大きくならないので)

容量が大きい方から辺を追加していき、その辺の容量を使い切るようなフローが存在する場合は、フローを流して辺を削除すればよい。
フローが存在するかの判定には Union-FInd Tree を用いて、辺を削除する場合は、辺の追加をキャンセルすることで実装すると見通しが良くなる。

#define L 2010
ll th[L]; // 3^i
	int findMaximum( int N, vector <int> A, vector <int> B ) {
		UF uf;
		uf.init(N);
		int m = A.size();
		th[0] = 1;
		rep(i, m) th[i+1] = th[i]*3%mod;
		ll res = 0;
		for(int i = m-1; i >= 0; i--){
			ll a = uf.find(0), b = uf.find(N-1), c = uf.find(A[i]), d = uf.find(B[i]);
			if((a==c&&b==d)||(a==d&&b==c)){
				(res+=th[i])%=mod;
			} else uf.unite(A[i], B[i]);
		}
		return res;
	}