AOJ 2748 - 夏合宿の朝は早い - ツバサの備忘録

解法

人を頂点、(起こす、起こされる)を辺としたグラフについて、強連結成分分解をして同一視される頂点は、一つにまとめることができます。
まとめる頂点集合を $S$ としたときに、まとめた結果新しくできる頂点全体で寝坊する確率は、
$\displaystyle \prod_{i \in S} (iが寝坊する確率)$
とすることができます。
強連結成分分解をした結果DAGになっているはずですが、そのDAGの中で、入次数が0の頂点集合 $T$ について、
$\displaystyle \prod_{i \in T} (1 - (iが寝坊する確率))$
を計算すると、求めるべき答えとなります。