夏合宿の朝は早い | JAG Domestic 2016

起こす人uから起こされる人vへ辺(u, v)を張るようなグラフを考える。このグラフは閉路があってややこしい。とりあえず強連結成分分解してみよう。各強連結成分において誰か一人でも起きれば、その強連結成分内において全員が必ず起きる。よって強連結成分S内の全員が起きる確率は、他の強連結成分の人たちから起こされることがなければである。更に、各強連結成分を1つの頂点につぶしたようなグラフを考える。ただし、自己ループの辺は取り除く。このグラフはDAGになっている。入次数が0の頂点は先程の数式のとおり。入次数が0の頂点の人々が全員起きた場合、このグラフはDAGになっているので、他の強連結成分の人々も全員起きることがわかる。よって、入次数が0の頂点の人々が起きる確率の積が解。

int N;
while (cin >> N, N) {
    vector<vi> G(N);
    vector<double> P(N);
    rep(a, N) {
        int m;
        cin >> P[a] >> m;
        rep(b, m) {
            int c;
            cin >> c;
            --c;
            G[a].push_back(c);
        }
    }
    TarjanSCC scc(G);
    vi indeg(N), cnt(N);
    vector<double> sleep(N, 1.0);
    rep(a, N) {
        cnt[scc[a]]++;
        sleep[scc[a]] *= P[a];
    }
    rep(a, N)each(b, G[a])if(scc[a]!=scc[b])indeg[scc[b]]++;
    double re = 1;
    rep(a, N)if (cnt[a] && !indeg[a]) {
        re *= 1 - sleep[a];
    }
    cout << re << endl;
}