AOJ 2748 : 夏合宿の朝は早い

夏合宿の朝は早い | Aizu Online Judge

確率は苦手…。システムの稼働率みたいに考えるのかなと思ったけど、
サンプルが単純な例で複雑なグラフになったとき結果がどうなるか分からず。
あきらめて解説を見る。

2016/Practice/模擬国内予選B/講評 - ACM-ICPC Japanese Alumni Group

解説があるのありがたい…。

解説が丁寧すぎて特筆すべきことがない。

強連結成分分解は以下のページを参考に実装した。

mathtrain.jp

前処理の「適当な頂点からdfs」について、
雑に選んでいいのかなと思って0からdfsしたら、
4つ目のサンプルでWAになった。

5
0.10 0
0.20 1 1
0.30 1 1
0.40 1 1
0.50 1 1

これが全部強連結として判定されてしまう。

しょうがないので↑のページでいうところの
t(v)に値が代入されていないときは再度その点から
dfsするようにしたらACできた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2364555#1

お世辞にもきれいな実装とは言えないので何とかしたい。