最大流問題 - ICPC突破専用ザク

過去に何回か手を付けたけどなぜか全く頭に入っていないので，Wikipediaの記事を参考にまとめる．
フローネットワーク - Wikipedia

有限な有向グラフ $G(V,E)$ の各枝 $(u,v) \in E$ に非負実数の容量 $c(u,v)$ が設定されているとする。 $(u, v) \not \in E$ の場合、 $c(u, v) = 0$ と見なす。ここで、2つの頂点、始点 $s$ と終点 $t$ を区別する。フローネットワークは実数関数 $f:V \times V \rightarrow \mathbb{R}$ で表され、全ノード $u$ と $v$ について、次が成り立つ。
・・・

辺に容量が与えられているので，容量オーバーしない程度にいくらくらいの量の水を流せるかという問題．
パラメータは3つの制約条件（容量制限，歪対称性，フロー保存則）を満たし，
そのうえでフロー $= \sum_{v \in V} f(s,v)$ を最大化させるのが目的．
色々アルゴリズムがあるっぽいけどフォード･ファルカーソンを見てみる．

フォード･ファルカーソンのアルゴリズム - Wikipedia
色々書いてるけど次のようなことを言ってる．

最初は $f(u,v)=0$ とする．

まだ水を流すことのできる辺だけをたどって $s$ から $t$ に行けるか見る．（ $s$ から $t$ への経路 $p$ で， $\forall (u,v) \in p , \,c(u,v)-f(u,v) > 0$ となるものがあるか）

実装は適当な探索（BFSとか）で．

もし可能ならそこに流せるだけの水( $=\min\{c(u,v)-f(u,v) ; (u,v) \in p\}$ )を流す．

無理なら終わる．

これだけ．
ここで，水は有向グラフの辺の逆向きにも流せることに注意したい．
たとえばある2つの頂点 $x_1,x_2$ がこの順でつながっていて， $c(x_1,x_2)=5, f(x_1,x_2)=3$ なら辺 $(x_1,x_2)$ には残り2まで水を流せるが，一方で辺 $(x2,x1)$ には3までの水を流し込める．
（既に水を流しているところに逆向きに流す感じ）