概要
最大流を計算するアルゴリズムよりも、グラフ構築や他の問題クラスとの関係を議論します。フローの具体的な計算方法であるFord FurkersonとかDinicの動作原理などは、インターネット上に腐るほど溢れているので、こういうのは言いません。
最近、フローを理解しようとしていたのだが、あまりにもいろいろな視点があるので混乱しています。皆さんには、僕の混乱を共有していただきます（強制）。
フロー
最大流は、グラフの辺に容量が定義されていて、その量だけ水を流せると考えた時、頂点$s$->頂点$t$にどれだけの水を流せるか？という問題です。最小費用流は、グラフの辺に容量と費用が定義されていて、頂点$s$->頂点$t$に水量$F$を流すことを考えた時、流した水の量と費用の積の和を最小化する問題です。
上の問題設定を聞くと、まるで道路交通網とか川の経路とか、見るからにグラフっぽいものにしか適用できないアルゴリズムで、僕には関係ないやろ、という印象を一般人に与えます。しかし実際には、かなり広範囲の問題がフローで解けます。具体的には、線形計画法・色塗り・割当・マッチングなどに関係があって、すごいです。画像処理とかでも使います（グラフカットという方法）。この記事では、ネットワークが云々…という設定の問題からスタートすると、まあ自明にフローなので、こういうのはどうでもいいとします。
フローに関する基本的な知識
最大流・最小カットは一致します（理由：一致するので）。
最大流と最小費用流は、全ユニモジュラ行列で記述された線形計画法に一致します。具体的には、全ての辺に対して変数$x_i$を割り当て、辺の容量が$u_i$だとしたら、制約条件として$0 \le x_i \le u_i$を追加します。各頂点一つ一つが制約条件となっており、[入ってくる辺の変数の総和]=[出て行く辺の変数の総和]という制約条件を追加します。最適化すべき量は、最大流の場合は頂点sから出る辺の変数の総和の$\max$です。最小費用流の場合は、全辺に定義されたコスト$c_i$に対して、辺に定義された変数$x_i$との内積$\displaystyle \sum_i c_i x_i$を最小化します。フローから構成された最適化問題は、必ず全ユニモジュラ行列で記述された線形計画法となり、必ず整数解を有します。
最大流は、最小費用流の特殊ケースです。具体的には、sから出ている辺にコスト$1$、他の辺にコスト$0$を割り当てます。このようなグラフの最小費用流は、最大流そのものです。
最小費用流では、流すべき水量$F$が固定となっていますが「F以下を流して」という制約に変更するためには頂点$s$から頂点$t$に容量無限費用$0$の辺を一本張るだけでよいです。Dangerous Towerが例題です。
フロー構築のための意味論
色塗り
「わっけわかんねえほど沢山の制約ドパァな問題を解く」（yosupoさん談）方法です。直感的にはこれが一番わかりやすかったです。
最大流の埋める燃やす問題への直感的解釈です。全頂点を$0, 1$に塗ることを想定します。頂点sを常に0, 頂点tを常に1が塗られているとします。任意の頂点対$(i, j)$を考えた時、$i=0, j=1$に塗られている時、辺$e_{i,j}$の容量のペナルティが課せられます。頂点が$n$点ある場合、全頂点の塗り方は$2^n$通りありますが、この中でペナルティが最も塗り分け方を探す、という問題が最大流アルゴリズムの多項式計算量で解くことができます。
解ける問題の例を出します。「ゴミA, B, Cが存在し、A, B, Cは燃やすか埋めるかします。ゴミXを埋めるのには$a_{X}$、燃やすのには$b_{X}$のコストがかかります。ここでゴミAを埋めずにゴミBを埋めると、世界が崩壊するのでそういうのは禁止です。最小コストは？」
燃やす場合はAに色0を塗り、埋める場合は色1を塗ると考えます。s->Xの容量は、ゴミXを埋める場合のコストとすればよいです（sは常に0で、Xが1の場合は埋めることを表すので）。X->tの容量は、ゴミXを燃やす場合のコストです。A->Bには無限大の容量の辺を張ります、これはAが埋めず(A=0)に、Bを埋める(B=1)の場合に、世界を崩壊するほどのコストを与えるためです。
しかしこの方法で、例えばしろくろチョコレートを解釈しようとすると、僕の脳のキャパオーバーします。
線形計画法(LP)
整数条件を含むLPは一般には多項式時間計算量では解けません。しかしそのLPがあるグラフを持ってきて、そのようなグラフでの最大流がLPに帰着ならば、最大流アルゴリズムによってLPを多項式計算量で解くことができます。
最大流は必ず整数解を有する線形計画法として記述することができます。埋める燃やす問題を始めとして、線形計画法を立式した後に気合で最大流のLPに帰着させることで、線形計画法を多項式時間で解くことができるようになります。hosさんの資料がわかりやすいです。
最大流問題をLPに帰着させます。各辺に実際に流れている水量を$x_i$とします。
$\max$ [$s$から直接出る辺に流れている水量の総和]
$s.t.$ 全ての頂点$v$について、[$v$に入る辺の水量の総和=$v$から出る辺の水量の総和]
これを以下のような線形計画法の形式にします。
$\max c^t x$
$s.t. x \ge 0, A x \le u$
すると、Aは必ず完全ユニモジュラ行列となり、$x$として必ず整数解が存在することが示せます。$A$が完全ユニモジュラであるとは、任意の小行列の行列式が0,±1になる行列だということです。
例として、埋める燃やす問題をフローで立式したものが、線形計画法であることを示します。次に、逆に、埋める燃やす問題をフローとは全く無関係に線形計画法で記述して、それを無理やりフローに帰着させてみます。
A, Bは必ず埋めるか燃やさなければなりません。Aを埋めるのには50円かかり、Aを燃やすのには30円かかります。Bを埋めるのには40円かかり、Bを燃やすのには70円かかります。Aを埋めずにBを埋めると100円かかります。
このような埋める燃やす問題は、頂点$s$, $t$, $v_A$, $v_B$を考えて、以下のようなグラフを構築します。
- 辺$s$->$v_A$に流量$A \le 50$
- 辺$v_A$->$t$に流量$\overline{A} \le 30$
- 辺$s$->$v_B$に流量$B \le 40$
- 辺$v_A$->$t$に流量$\overline{B} \le 70$
- 辺$v_A$->$v_B$に流量$C \le 100$
この最大流が、埋める燃やす問題の解となります。
今、流量をもととして、気合でLPを構築してみます。すると、
\begin{align}
\text{maximize } & A+B \\
\text{subject to } & 0 \le A \le 50 \\ & 0 \le \overline{A} \le 30 \\ & 0 \le B \le 40 \\ & 0 \le \overline{B} \le 70 \\ & 0 \le C \le 100 \\ & A = \overline{A}+C \\ & \overline{B} = B+C
\end{align}
\begin{align}
\text{maximize } & A+B \\
\text{subject to } & 0 \le A \le 50 \\ & 0 \le \overline{A} \le 30 \\ & 0 \le B \le 40 \\ & 0 \le \overline{B} \le 70 \\ & 0 \le C \le 100 \\ & A - \overline{A}-C \le 0 \\ & \overline{B} - B-C \le 0
\\ & -A + \overline{A}+C \le 0 \\ & -\overline{B} + B+C \le 0
\end{align}
\begin{align}
\text{maximize } & \begin{pmatrix} 1&1&0&0&0 \end{pmatrix} \begin{pmatrix} A \\ B \\ \overline{A} \\ \overline{B} \\ C \end{pmatrix} \\
\text{subject to } & 0 \le \begin{pmatrix} A \\ B \\ \overline{A} \\ \overline{B} \\ C \end{pmatrix} \\ & \begin{pmatrix} 1&0&0&0&0 \\ 0&1&0&0&0 \\ 0&0&1&0&0 \\ 0&0&0&1&0 \\ 0&0&0&0&1 \\ 1&0&-1&0&1 \\ -1&0&1&0&1 \\ 0&-1&0&1&-1 \end{pmatrix} \begin{pmatrix} A \\ B \\ \overline{A} \\ \overline{B} \\ C \end{pmatrix} \le \begin{pmatrix} 50\\40\\30\\70\\100\\0\\0\\0\\0 \end{pmatrix}
\end{align}
変数を割り当てます。
\begin{align}
\text{maximize } & c^T x \\
\text{subject to } & 0 \le x \\ & A x \le u
\end{align}
双対取ります。$y=(y_1, ..., y_9)^t$
\begin{align}
\text{minimize } & y^t u \\
\text{subject to } & 0 \le y \\ & y^t A \ge c
\end{align}
\begin{align}
\text{minimize } & 50 y_1+40 y_2+30 y_3+70 y_4+100 y_5 \\
\text{subject to } & 0 \le y \\ & y_1 + y_6 - y_8 \ge 1 \\& y_2+y_7-y_9 \ge 1 \\& y_3-y_6+y_8 \ge 0 \\& y_4-y_7+y_9 \ge 0 \\& y_5-y_6+y_7+y_8-y_9 \ge 0
\end{align}
$z_1=y_6-y_8, z_2=y_7-y_9$と置きます。
\begin{align}
\text{minimize } & 50 y_1+40 y_2+30 y_3+70 y_4+100 y_5 \\
\text{subject to } & 0 \le y \\ & y_1 + z_1 \ge 1 \\& y_2+z_2 \ge 1 \\& y_3-z_1 \ge 0 \\& y_4-z_2 \ge 0 \\& y_5-z_1+z_2 \ge 0 \\& z_1, z_2 \in \mathbf{R}
\end{align}
なんか良くわからない最適化問題が出ました。$z_1$は、スイッチの役割をしています。$z_1=0$ならば$y_1=1, y_3=0$で、$z_1=1$ならば$y_1=0, y_3=1$です。同様に$z_2$は$y_2, y_4$のスイッチです。$y_5$に関する制約条件は、$z_1=1, z_2=0$の時に$y_5=1$となり、他の時は$y_5=0$です。
つまり、$y_1=1$が「Aを埋める」、$y_3=1$が「Aを埋めない」、$y_2=1$が「Bを埋める」、$y_4=1$が「Bを埋めない」、$y_5=1$が「Aを埋めずにBを埋める」という意味になっていますね。
逆に、線形計画法からフローを導出します。変数$A, \overline{A}, B, \overline{B}, C$を定義します。Aを埋めるなら$A=1$、Aを埋めないなら$\overline{A}=1$、Bを埋めるなら$B=1$、Bを埋めないなら$\overline{B}=1$、Aを埋めずにBを埋めるなら$C=1$とします。これに、背反の条件やandの条件を考慮すると、以下のようなLPを立式することができます。
\begin{align}
\text{minimize } & \begin{pmatrix} 50&40&30&70&100 \end{pmatrix} \begin{pmatrix} A \\ B \\ \overline{A} \\ \overline{B} \\ C \end{pmatrix} \\
\text{subject to } & 0 \le \begin{pmatrix} A \\ B \\ \overline{A} \\ \overline{B} \\ C \end{pmatrix} \\ & \begin{pmatrix} 1&0&1&0&0 \\ -1&0&-1&0&0 \\ 0&1&0&1&0 \\ 0&-1&0&-1&0 \\ 1&-1&-&0&1 \end{pmatrix} \begin{pmatrix} A \\ B \\ \overline{A} \\ \overline{B} \\ C \end{pmatrix} \ge \begin{pmatrix} 1\\-1\\1\\-1\\0 \end{pmatrix}
\end{align}
双対取ります。$x=(x_1, ... x_5)$
\begin{align}
\text{maximize } & x_1-x_2+x_3-x_4 \\
\text{subject to } & 0 \le x \\ & \begin{pmatrix} 1&0&1&0&0 \\ -1&0&-1&0&0 \\ 0&1&0&1&0 \\ 0&-1&0&-1&0 \\ 1&-1&-&0&1 \end{pmatrix}^T x \le \begin{pmatrix} 50\\40\\30\\70\\100 \end{pmatrix}
\end{align}
\begin{align}
\text{maximize } & x_1-x_2+x_3-x_4 \\
\text{subject to } & 0 \le x \\ & x_1-x_2+x_5 \le 50 \\& x_3-x_4-x_5 \le 40 \\& x_1-x_2 \le 30 \\& x_3-x_4 \le 70 \\& x_5 \le 100
\end{align}
今、$x_A=x_1-x_2+x_5, x_B=x_3-x_4-x_5, x_{\overline{A}} = x_1-x_2, x_{\overline{B}}=x_3-x_4, x_C = x_5$と定義する。すると、
x_A-x_{\overline{A}}-x_C=0 \\
x_B-x_{\overline{B}}+x_C=0 \\
であり、
\begin{align}
\text{maximize } & x_A+x_B \\
\text{subject to } & 0 \le x \\ & x_A \le 50, x_{\overline{A}} \le 30, x_B \le 40, x_{\overline{B}} \le 70, x_C \le 100
\\& x_A-x_{\overline{A}}-x_C=0 \\& x_B-x_{\overline{B}}+x_C=0
\end{align}
なる最適化問題が生えます。これは眺めていると最大流問題のLP形式であることがわかります。以上から、LPで立式したものから最大流問題へと帰着することができました。
このことで、LPと最大流を相互に行き来することによって、気合があれば、簡単に立式可能なLPから、何とかフローに帰着できることがわかりました。
離散説明変数の大量の制約条件
辺に命題を割り当てて、満たされる命題数を最大化することができます。
例として、しろくろチョコレートを考えます。$i$をEvenなマスの添字、$j$をOddなマスの添字とします。説明変数$x_{ij}$を「i, jをセットにして取る」とします。すると$i$, $j$のマスはひとつしかないという制約条件から、$\displaystyle \sum_i x_{ij}=1, \sum_j x_{ij}=1$です。これをグラフとして構築して、最大流を流すとマッチングの最大値が求まります。
似たように、SRM 717 Div.1 Easy構築問題を考えます。この問題では、完全無向グラフに向きを割り当てた時、全頂点の出次数$a_i$が与えられるので、グラフを再構成する問題です。説明変数$x_{ij}$を「辺の向きが、頂点$i$から頂点$j$への方向である」とします。すると、出次数の制約条件から、$\displaystyle \sum_i x_{ij}=a_i$です。これをグラフとして構築して、最大流を流すと最大流が$n-1$になり、それを流せるような流し方が具体的な構築となります。
Atcoder ABC005D マーブルでは、各盤面に置くことができる石の数が1つであるという制約条件があります。石をある場所に移動するコストが定義されているので、制約を満たしながら石の移動コストを最小化します。説明変数$x_{ij}$を「石種類iを座標$j$に置く」と定義します。制約条件として、石種類Aの数が$n_A$なので$\displaystyle n_A = \sum_j x_{Aj}$, 石種類Aの数が$n_B$なので$\displaystyle n_B = \sum_j x_{Bj}$, 石種類Cの数が$n_C$なので$\displaystyle n_C = \sum_j x_{Cj}$です。更に、ひとつの座標にはひとつの石しか置けないので、$\displaystyle \sum_i x_{ij} = 1$です。これをグラフとして構築して、最大流である$n_A+n_B+n_C$を流した時の最小費用が答えになるので、最小費用流になります。
割当
フローといえば割当という感じで語られることが多いですが、よくわかりません。離散説明変数の大量の制約条件として解釈しないと、僕は理解できませんでした（あるいは、それが「割当」と呼ばれているものなのかもしれませんが）。例題はDangerous Towerです。
最小カット
とりあえずそれっぽいグラフを作ってみて、その最小カットで切られたところ選択される、という真っ当な解釈が可能です。理論だって作ることはできない感じがするので、この場合試行錯誤でグラフを構成することになると思います。
この解釈での解説は、診断人さんの資料が非常にわかりやすいです。
階段関数の線形結合和の最適化
階段関数$f(x) = (0 \le x\ ?\ 1 : 0)$を定義します。$x_s = 0, x_t= 1$として、全コスト・制約条件を一つの最大化問題として立式します。$c_{ij}$を正の係数として、以下を立式します。
$\displaystyle\max \sum_{i, j} c_{ij} f(x_i - x_j)$
するとkomiyamさんの解説によると、$i, j$に容量$c_{ij}$の辺が張られているグラフの最大流が、その最大値を実現すると主張されています。
しかし、容量$0$の辺を作らなければいけない時に、この構成方法では正しいグラフが構成できません。埋める燃やす問題で、$A$を燃やすのにはコストがかからない、などだと$\max$関数の中に$0 \times f(x_A - x_s)$を線形和に追加しなければいけませんが、これはなくても同様の立式が可能となってしまいます。よくわからないです。
二部グラフ
盤面を市松模様に二部グラフに分けることによって初めて、グラフがいい感じに構成できるケースがあります。これは頂点$i, j$について、$i$に$0$が塗られていて$j$が$1$が塗られている、という非対称性のせいで全てを同じものとして扱うといい感じにグラフが作れないから、くらいで認識しています。
例として、しろくろチョコレート、診断人さんの資料のGCJ Final 2008 E、SRM 558 Div.1 Hardなどがあります。
何が言いたかったの？
いや、別に…