Codeforces Round #532 (Div. 2) - E. Andrew and Taxi
バチャ中に解けなかったけど、おもしろかった。
解説
実はコストに関する二部探索でいい。
あるコストを決め打ったときに、より大きい辺のみで、グラフを構築して、それがDAGであればokそうじゃなければngっていう二部探索をしよう!
この時DAGであれば、必ず条件を満たすように構築できる。
まずトポロジカルソートをする。トポロジカルソートしたとき、コスト以下の辺は必ず添え字が若いほうから年寄りの方向に結べば当然閉路はできない。
よって解くことができました。
提出コード
まとめ
数字が小さいほうから大きいほうみたいに決めて閉路をつくらない構築たびたび見る気がする。