AOJ 2748 夏合宿の朝は早い
問題概要
人それぞれの寝坊する確率と、連絡先を知っている人が与えられる。
起きた人が連絡先を知っている人すべてにモーニングコールをするとき、全員が起きられる確率を求めよ。
解法
- 誰にも起こしてもらえない人（誰にも連絡先を知られていない人）は自分で起きなければならない
- ループしている人は、確率をまとめて1人として扱って良い
よって、連絡先を知っているという関係を有向辺にしてグラフで表現して、強連結成分（どの2頂点間も互いに行き来可能）を1つにまとめたグラフをつくり（強連結成分分解）、入次数が0の頂点の確率をかけてあげれば良い。
具体的な実装方針は
- 強連結成分を調べるために、各頂点からdfsをしてあげて、互いに行き来可能な頂点同士をUnion-Find木で管理する（親が等しい頂点同士は同じ強連結成分に属する）
- 各強連結成分ごとの確率を調べ、その強連結成分の入次数が0ならば、確率を答えにかけあわせる
計算量は、dfsパートは辺の数は高々 本なので
、Union-Find木を構成するパートは
、強連結成分ごとの確率を求めるのと入次数が0かどうか調べるパートが
なので、全体で
になる。
が小さいので間に合う。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2770535#1
