ICPC模擬国内2016b:D 夏合宿の朝は早い

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748&lang=jp

問題

各頂点が確率を重みとして持つような頂点からなる有向グラフが与えられる。
また、各頂点は確率で状態Aとなる。状態Aとなった頂点は、隣接する頂点の状態をAに変えることが出来る。
何も状態が振られていない状況を考えて、次の瞬間に割り当てられた確率で状態Aに遷移したとする。
このとき、全ての頂点が状態Aとなっている確率を求めよ。ただし、頂点Aが隣接する頂点をAに変化させる処理は一瞬で終わるものとする。

(追記)AはAwakeということにしておいてください。

解法

まず、自明でない最も簡単な場合について考えてみます。(下の図参照)

このような場合は、入次数が0の頂点がAに遷移すればその下流の頂点はどんな状態でも良いです。
実際に確かめてみると



となるので確かめることができました。(確率であることに注意すれば容易にわかります)

次に、誰かがAに遷移しなくてもなんとかなりそうな場合で、最も冗長性が高い場合を考えましょう。(これはサイクルです、強連結成分と言ってもいいです)

どれかがAに遷移すれば良いので、この強連結成分がAに遷移する確率を求めるには、どれもAに遷移しない場合の余事象を取ればいいです。
上の図については、 で求められます。

さて、上の考察をあわせて考えてみます。1つ目の図の頂点vを強連結成分と思うことにしましょう。すると、強連結成分の確率だけが答えに影響します。
つまり、強連結成分を頂点と見立てて構築しなおしたグラフの入次数が0の頂点に付けられた確率のみが答えに影響します。
入次数が0の頂点は、自力でAに遷移しないと条件を満たさないので、そういった頂点が同時にAに遷移すれば良いです。
を入次数0の頂点に付けられた確率とすると

とすれば答えが求まります。

実装

強連結成分分解をして、頂点に彩色します。
同じ色に彩色された頂点は、同じ強連結成分に含まれるので、強連結成分内にある頂点の確率の総積をとれば構築しなおしたグラフに含まれる頂点の確率が求まります。
次に、構築しなおしたグラフの入/出次数を調べます。最後に、入次数が0の頂点に付けられた確率の総積をとれば答えです。

因みに、強連結成分分解をする際に使用したコードはこれです。
強連結成分分解 - yrfw

コード

AIZU ONLINE JUDGE: Code Review

int n;

void solve() {

    vector<vector<int>> G(n);
    vector<double> p(n);

    for (int i = 0; i < n; i++) {
        cin >> p[i];

        int friend_n;
        cin >> friend_n;
        for (int j = 0; j < friend_n; j++) {
            int to; cin >> to;
            G[i].push_back(to-1);
        }   
    }

    
    StronglyConnectedComponents scc(G);
    scc.color_graph();
    vector<int> color = scc.nd_color;
    vector<vector<int>> H = scc.build();

    //彩色数
    int color_n = 0;
    for (auto c : color) color_n = max(color_n, c + 1);


    //強連結成分内での確率
    vector<double> group_p(color_n, 1);
    for (int i = 0; i < n; i++) {
        group_p[color[i]] *= p[i];
    }


    //in/out
    vector<pair<int, int>> degree(color_n);
    for (int v = 0; v < color_n; v++) {
        for (auto nv : H[v]) {
            //v -> nv
            degree[v].second++;
            degree[nv].first++;
        }
    }

    double ans = 1;

    for (int i = 0; i<color_n; i++) {
        int in = degree[i].first;
        int out = degree[i].second;
        if (in == 0) ans *= (1 - group_p[i]);
    }


    cout << fixed << setprecision(9) << ans  << endl;  
}


int main() {
    while (1) {
        cin >> n;
        if (n == 0) break;
        solve();
    }
}