最大流問題 [いかたこのたこつぼ]

いきなり逆辺なんて出てきて「何じゃこりゃ」と思うが、これを使うと貪欲法（見つかった経路に最大限流す、を繰り返す）が上手くいく。 逆辺の無い貪欲法で解くと、経路を発見する順番によっては最大を達成できなくなる場合がある。 逆辺の無いネットワーク ① -9→ ② ｓ→ｔの経路をどれか1つ見つける際、 10↗ ＼6 ＼8 ｓ-①-④-ｔの経路を最初に見つけてしまうと…… ／ ↘ ↘ 流量４を流した結果、④-ｔのリンクがそれ以上使えなくなる ｓ-4→ ③ -3→ ④ -4→ｔ （下図:ｓ-①-④-ｔに流量4を流した後の残容量） ① -9→ ② 6↗ ＼2 ＼8 最適解は、経路ｓ-①-②-ｔに多めに流すことで ／ ↘ ↘ 経路ｓ-①-④-ｔに流す容量を少なくし、 ｓ-4→ ③ -3→ ④ -0→ｔ リンク④-ｔを経路ｓ-③-④-ｔのために開けておくのが良い 逆辺を張ったネットワーク（正方向残容量/逆方