WARush

SRMの結果とか、解けた問題のコードを書いていきます

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)を上回る。これはつまり・・・どうゆうことだってばよ?

答えをチラ見

大きい流量を持つ辺から見て行って、辺が持つ流量が流せるかどうかを試す。もし流せるようならそれをフローとして確定してしまってよい。その際に、その辺を削除するだけでフローをどこにどれだけ流したかは気にする必要はない。らしい!

下の図を見て欲しい
f:id:Ekaing:20150517023404j:plain
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

頂点が少なくて、辺が多いときの事を考えてなかった・・

答えをチラ見・その2

いきなり完全なグラフを持つんじゃなくて、大きな辺から順番に追加していき、その都度流せるか試せばよい。らしい!

なるほど・・・orz

変形ダイクストラとかでもいけそうね


ソースコード

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;
    }
};