Google Code Jam 2019 Round2 : Contransmutation

問題. Contransmutation

$N$ 種類の金属があり，1番目の金属は鉛である． $i$ 番目の金属を1グラム使用して， $R_{i_1}$ 番目と $R_{i_2}$ 番目の金属をそれぞれ1グラム生成できる．最初に $i$ 番目の金属は $g_i$ グラムある．金属の生成方法を繰返し行い鉛のグラム数を最大化せよ．そして，そのときの鉛の最大グラム数の $10^9 + 7$ による剰余を答えよ．ただし，鉛を無限に生成できるときは "UNBOUNDED" と答えよ．

制約： $2 \le N \le 10^5$ ，　 $0 \le g_i \le 10^9$

解法．強連結成分分解

$i$ 番目の金属を頂点 $v_i$ として，弧を $(v_i, v_{R_{i_1}}), (v_i, v_{R_{i_2}})$ を加えた有向グラフ $G$ を考える． $G$ を強連結成分分解して，その強連結成分全体を $(C_1, C_2, \ldots, C_k)$ とする．ただし，添字の昇順にトポロジカルソートされているとする．各強連結成分 $C_i$ 内で生成を行うと， $|C_i|$ が1でない限り $C_i$ 内の総グラム数が減ることはない．また， $C_i$ 内に含まれる弧数の方が $|C_i|$ よりも真に大きい場合は $C_i$ 内の総グラム数は真に増加することが分かる．したがって， $C_i$ 内に最初のグラム数が正の頂点が存在するか， $j < i$ で $C_j$ から $C_i$ への道が存在して $C_j$ 内に最初のグラム数が正の頂点が存在する場合に， $C_i$ 内のすべての頂点は無限に生成することができる．
各頂点の出次数はちょうど 2 なので，弧数は頂点数のちょうど 2 倍となる．したがって，強連結成分分解は $O(N)$ 時間で求まるので，頂点 $v_1$ が無限に生成可能かどうかは $O(N)$ 時間で判定できる．

次に， $v_1$ が無限に生成できない場合に最大で何グラム得ることができるかを考える． $v_1$ を含む強連結成分を $C_i$ とする．このとき，強連結成分 $C_j \, (j \le i)$ 内の頂点 $v_{j_1}$ を分解して $v_1$ のグラム数を増やすことを考える． $(C_1, C_2, \ldots, C_k)$ の成分グラフを $G'$ とする．ただし， $G'$ は多重辺を含むとする．このとき， $C_j$ から $C_i$ への $G'$ 上の異なる道の数を $p$ とすると， $v_1$ は $v_{j_1}$ によって $p \times g_{j_1}$ グラムだけ増加する．

計算時間： $O(N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;

struct Graph {
    const int n;
    std::vector<std::vector<int>> adj, radj;
    std::vector<int> scc;

    explicit Graph(int _n) : n(_n), adj(n), radj(n), scc(n, false) {}

    void add_edge(const int src, const int dst) {
        adj[src].push_back(dst); radj[dst].push_back(src);
    }

    void Dfs(const int cur, std::vector<int> &ord) {
        scc[cur] = true;
        for (auto dst : adj[cur])
            if (!scc[dst]) Dfs(dst, ord);
        ord.push_back(cur);
    }
    void RevDfs(const int id, const int cur) {
        scc[cur] = id;
        for (auto dst : radj[cur])
            if (scc[dst] == -1) RevDfs(id, dst);
    }

    void StronglyConnectedComponents() {
      std::vector<int> ord; ord.reserve(n);
        for (int v = 0; v < n; ++v)
            if (!scc[v]) Dfs(v, ord);

        std::fill(scc.begin(), scc.end(), -1);
        for (int i = n - 1, no = 0; 0 <= i; --i)
            if (scc[ord[i]] == -1) RevDfs(no++, ord[i]);
    }
};

/********************************************************************/
class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> N;
        g = new Graph(N);
        for (int v = 0; v < N; ++v) {
            for (int i = 0, u; i < 2; ++i) {
                cin >> u;
                g->add_edge(v, u - 1);
            }
        }

        gram.resize(N);
        for (auto &&x : gram) cin >> x;
    }
    void print() {
        cout << "Case #" << num_case << ": ";
        if (max_gram == -1) cout << "UNBOUNDED\n";
        else cout << max_gram << "\n";

        delete g;
    }
    void solve();

private:
    // define variable
    const int num_case;

    int N;
    Graph *g;
    vector<ll> gram;

    ll max_gram = 0;
};

void Solver::solve() {
    g->StronglyConnectedComponents();

    const int num_comp = *max_element(g->scc.begin(), g->scc.end()) + 1;
    vector<vector<int>> comp(num_comp);
    for (int v = 0; v < N; ++v) comp[g->scc[v]].push_back(v);

    vector<size_t> num_edges(num_comp);
    for (int c = 0; c < num_comp; ++c) {
        for (int v : comp[c]) {
            for (int u : g->adj[v])
                if (g->scc[u] == c) ++num_edges[c];
        }
    }

    vector<bool> inf(num_comp, false);
    vector<ll> num_path(num_comp, -1);
    for (int c = num_comp - 1; 0 <= c; --c) {
        if (c == g->scc[0]) {
            num_path[c] = 1;
        }
        else {
            for (int v : comp[c])
                for (int u : g->adj[v]) {
                    if (num_path[g->scc[u]] != -1) {
                        if (num_path[c] == -1) num_path[c] = num_path[g->scc[u]];
                        else (num_path[c] += num_path[g->scc[u]]) %= MOD;
                    }
                    inf[c] = inf[c] or inf[g->scc[u]];
                }
            if (num_path[c] != -1 && 0 < num_edges[c])
                inf[c] = true;
        }

        if (num_path[c] != -1 && comp[c].size() < num_edges[c])
            inf[c] = true;
    }

    for (int v = 0; v < N; ++v) {
        if (0 < gram[v]) {
            const int k = g->scc[v];
            if (inf[k]) { max_gram = -1; break; }
            else if (num_path[k] != -1) (max_gram += (gram[v] * num_path[k]) % MOD) %= MOD;
        }
    }
}
/********************************************************************/

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(4) << setiosflags(ios::fixed);

    int T; cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}