BOJ 28360 - 양동이 게임

BOJ 28360 - 양동이 게임

항상 더 수가 큰 양동이 쪽으로 떨어지므로 $dp$ 를 이용해서 푼다.

$i$ 에서 수가 더 큰 이어진 양동이들로 자신의 간선 개수만큼 자신의 $dp$값을 나눠서 전달해주면 된다.

간선이 없는 양동이들 중 가장 큰 값이 정답이다.

#define double long double
void solve() {
   int n, m;
   cin >> n >> m;
   vvi edges(n + 1);
   while (m--) {
      int v, w;
      cin >> v >> w;
      assert(v < w);
      edges[v].pb(w);
   }

   vector<double> dp(n + 1);
   dp[1] = 100;
   for (int i = 1; i <= n; i++) {
      for (int j: edges[i]) {
         dp[j] += dp[i] / sz(edges[i]);
      }
   }
   double ans = 0;
   for (int i = 1; i <= n; i++) {
      if(sz(edges[i]) == 0) maxa(ans, dp[i]);
   }
   cout << setprecision(12) << fixed << ans;
}