AOJ2594 Reverse Roads
解法
与えられるネットワークに対して、与えられた辺の逆向きの辺を元のネットワークに加えた(無向)ネットワークを考えると、このネットワークの最大フローが求めたい最大フローである。
これは、2頂点間に張られた辺はどちらかしか使われないということを考えれば分かる。
逆向きの辺が使われたかどうか調べたければ、最初に逆向きの辺を記録しておき、その辺のcapが0(逆辺のcapが1)になっていることを確かめればよい。(よくあるフローの復元の話)
コード
与えられるネットワークに対して、与えられた辺の逆向きの辺を元のネットワークに加えた(無向)ネットワークを考えると、このネットワークの最大フローが求めたい最大フローである。
これは、2頂点間に張られた辺はどちらかしか使われないということを考えれば分かる。
逆向きの辺が使われたかどうか調べたければ、最初に逆向きの辺を記録しておき、その辺のcapが0(逆辺のcapが1)になっていることを確かめればよい。(よくあるフローの復元の話)