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