Codeforces Round #532 (Div. 2) - E. Andrew and Taxi

問題リンク

バチャ中に解けなかったけど、おもしろかった。

解説

実はコストに関する二部探索でいい。

あるコスト cを決め打ったときに、 cより大きい辺のみで、グラフを構築して、それがDAGであればokそうじゃなければngっていう二部探索をしよう!

この時DAGであれば、必ず条件を満たすように構築できる。

まずトポロジカルソートをする。トポロジカルソートしたとき、コスト c以下の辺は必ず添え字が若いほうから年寄りの方向に結べば当然閉路はできない。

よって解くことができました。

提出コード

codeforces.com

まとめ

数字が小さいほうから大きいほうみたいに決めて閉路をつくらない構築たびたび見る気がする。