ICPC2016 模擬国内予選B D 夏合宿の朝は早い
解法
強連結成分分解して、最上流の強連結成分の中で誰かが起きれば、強連結成分内の人も、その下流の人も起きる。
コード
#include <bits/stdc++.h> using namespace std; int N; vector<int> SCC(const vector<vector<int>> &g, const vector<vector<int>> &rg) { vector<bool> used(N, false); vector<int> cmp(N, -1); vector<int> vs; function<void(int)> dfs = [&](int v) { used[v] = true; for (int w : g[v]) if (!used[w]) dfs(w); vs.push_back(v); }; function<void(int, int)> rdfs = [&](int v, int k) { used[v] = true; cmp[v] = k; for (int w : rg[v]) if (!used[w]) rdfs(w, k); }; for (int i = 0; i < N; ++i) if (!used[i]) dfs(i); used.assign(N, false); int k = 0; for (int i = vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) rdfs(vs[i], k++); return cmp; } double solve(const vector<vector<int>> &g, const vector<vector<int>> &rg, const vector<double> &P) { vector<int> cmp = SCC(g, rg); int ma = *max_element(cmp.begin(), cmp.end()); double ans = 1.0; for (int cmp_value = 0; cmp_value <= ma; ++cmp_value) { // Check for top bool top = true; for (int i = 0; i < N; ++i) { if (cmp[i] != cmp_value) continue; for (int rv : rg[i]) if (cmp[rv] >= 0 && cmp[rv] < cmp_value) top = false; } if (!top) continue; double q = 1.0; // All group members cant wake up for (int i = 0; i < N; ++i) { if (cmp[i] == cmp_value) q *= P[i]; } ans *= (1.0 - q); } return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); while (true) { cin >> N; if (N == 0) break; vector<double> P(N); vector<vector<int>> g(N); vector<vector<int>> rg(N); for (int i = 0; i < N; ++i) { cin >> P[i]; int n; cin >> n; while (n--) { int a; cin >> a; a--; g[i].push_back(a); rg[a].push_back(i); } } printf("%.15f\n", solve(g, rg, P)); } }