n-knuu's logs

憧れ駆動。だいたい競プロ

AOJ2594 Reverse Roads

解法

与えられるネットワークに対して、与えられた辺の逆向きの辺を元のネットワークに加えた(無向)ネットワークを考えると、このネットワークの最大フローが求めたい最大フローである。
これは、2頂点間に張られた辺はどちらかしか使われないということを考えれば分かる。

逆向きの辺が使われたかどうか調べたければ、最初に逆向きの辺を記録しておき、その辺のcapが0(逆辺のcapが1)になっていることを確かめればよい。(よくあるフローの復元の話)

コード


感想

フローの復元の話まで入っている教育的問題だった。
実際、解説スライド(url)にも、ライブラリデバッグ用と書いてあるし、当時(2011年)はそこまでフローのライブラリを整備してなかった人も多かったのかもしれない?
(まあでも蟻本第一版は2010年だしそんなこともなさそうな気もするけど、全体の底上げとしては良さそう)