SRM632 Div1 Medium "CandyCupRunningCompetition"
考えたこと
最大流問題だけど、いかんせん流量がでかすぎる・・(最大3^2000)
それぞれの辺の流量は、3^0, 3^1, 3^2...3^n-1, 3^nという具合に割り当てられており、ある流量(3^x)はそれ以外の全ての流量の総和(3^0 + 3^1 + 3^2 + ... + 3^x-1)を上回る。これはつまり・・・どうゆうことだってばよ?
答えをチラ見
大きい流量を持つ辺から見て行って、辺が持つ流量が流せるかどうかを試す。もし流せるようならそれをフローとして確定してしまってよい。その際に、その辺を削除するだけでフローをどこにどれだけ流したかは気にする必要はない。らしい!
下の図を見て欲しい
3^5..は流すことは無理で、3^4はいけました!という状況。
流量3^4を3^5を使用して流しているが、この辺に3^4を流したところで3^3以下の流量を考えるにあたって何の影響もない。また、3^4の辺を3^3以下の流量の辺を考えるときに利用できなくなるが、3^0 + 3^1 + 3^2 + 3^3 < 3^4のため、3^4を流してしまうのが最善である。
いざ実装
DFSで、SからTに到達できる最も大きな辺を返すような実装にしよう。
TLE
頂点が少なくて、辺が多いときの事を考えてなかった・・
ソースコード
class E { public: E(int _to, int _cost) { to = _to; cost = _cost; } int to, cost; }; const int INF = 2050; const long long MOD = 1000000007; long long pow3mod[2050]; bool del[2050], used[2050]; vector <E> G[2050]; int N; class CandyCupRunningCompetition { public: int findMaximum(int _N, vector <int> A, vector <int> B) { N = _N; int M = A.size(); // 剰余 pow3mod[0] = 1; for (int i = 1; i <= M; i++) { pow3mod[i] = pow3mod[i - 1] * 3 % MOD; } long long ans = 0; for (int i = M - 1; i >= 0; i--) { // エッジ追加 G[A[i]].push_back(E(B[i], i)); G[B[i]].push_back(E(A[i], i)); for (int j = 0; j < N; j++) used[j] = false; // たどり着ける場合 if (dfs(0)) { // 答えに足す ans += pow3mod[i]; ans %= MOD; // エッジ削除 del[i] = true; } } return (int)ans; } // vからスタートしてゴールまで到達できるか? bool dfs(int v) { if (v == N - 1) return true; used[v] = true; bool ret = false; for (int i = 0; i < G[v].size(); i++) { E e = G[v][i]; if (del[e.cost]) continue; if (used[e.to]) continue; ret |= dfs(e.to); } return ret; } };