短い版をこちら に書きました．
背景
ネットワークフローを勉強してみよう，と思っていたところで，グラフの最小カット問題に行き当たりました．診断人さんの『最小カットを使って「燃やす埋める問題」を解く』 というスライドがたいへん親切にわかりやすく書かれていて，勉強になりました．ただ，「考えて選択肢の順番を決めないといけない」(スライド35) というところが難しく感じました．
次に，よすぽさんのblog記事「最小カットについて」 を読みました．最小カットで解ける問題とは，要するに次のタイプだ，というまとめに，なるほど，と思いました．
- 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない
- 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する
- 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある
- 罰金の最小値は？
ただ，その記事の後ろに出てきますように，「Xが赤で、Yが赤の時にZ円の報酬」や「Xが青で、Yが青の時にZ円の報酬」も扱えるわけです．もちろんその記事に詳述されているのですが，自分なりの理解をしたいな，と思い，以下のように整理しました．
本質的には，お二人の説明と何も変わっているところはありませんが，自分としては，問題への適用方針がはっきりできたような気がしています．
一般形
次の形をしている問題が，最小カットによって解ける燃やす埋める問題です．
- ある条件が満たされたときに (正の量を) 支払う．ある条件が満たされたときに (正の量を) 受け取る．支払を最小 (あるいは受取りを最大) にせよ，という形で問題が規定されている．
- 適当な命題の集合 $P_0$ が，以下の条件を満たすように定義できる．
- $P_0$ は，True (真) と False (偽) を含む．
- 「支払う」タイプの条件は，$Q \subseteq P_0$ と $R \subseteq P_0$ を使って，「$Q$のうち1つ以上が成り立ち，しかも，$R$のうち1つ以上が成り立たない」と記述できる．論理式で書けば，$\bigvee_{q \in Q} q \land \bigvee_{r \in R} \neg r$ となる．
- 「受取る」タイプの条件は，$Q \subseteq P_0$ と $R \subseteq P_0$ を使って，「$Q$のすべてが成り立つか，または，$R$のすべてが成り立たない」と記述できる．論理式で書けば，$\bigwedge_{q \in Q} q \lor \bigwedge_{r \in R} \neg r$
ただし，$Q$, $R$ は空ではないことにします．
$P_0$ をうまく決定できれば，あとは後述する方法に従って機械的に解ける，ということになります．
良く現れる形
一般には，$Q$ と $R$ を使って上のように表現できますが，頻出するのは次の形かと思います．
$p$, $q$ を $P_0$ の命題とします．
支払う条件
- p が成り立つ ($p$)
- p が成り立たない ($\neg p$)
- p が成り立ち，q が成り立たない ($p \land \neg q$)
- p か q の少なくとも一方が成り立つ ($p \lor q$)
- p か q の少なくとも一方が成り立たない ($\neg p \lor \neg q$)
受取る条件
- p が成り立つ ($p$)
- p が成り立たない ($\neg p$)
- p が成り立たないか，q が成り立つ ($\neg p \lor q$)
- p と q の両方が成り立つ ($p \land q$)
- p か q の両方が成り立たない ($\neg p \land \neg q$)
たとえば，支払う条件の一般形で，$Q = \{p\}$, $R = \{False\}$ としますと，1番目に挙げた「pが成り立つ」が得られますし，$Q = \{True\}$, $R = \{p, q\}$ としますと，5番目に書いた「pかqの少なくとも一方が成り立たない」が得られます．
適用例．その1
MUL
AtCoder Regular Contest 085 の 問題E. MUL です．表現しなければならない規程は以下の通りです．
- $i$ が $j$ の約数である時，宝石 $i$ を割ったら，宝石 $j$ を割らなければならない．
- $a_i > 0$ なる $i$ について，宝石 $i$ が割られなければ，$a_i$ 受取る．
- $a_i < 0$ なる $i$ について，宝石 $i$ が割られなければ，$- a_i$ 支払う．
使用する命題の集合 $P_0$ は，次の命題の全体とします．
- $p_i$ ... 宝石 $i$ を割る．
すると，3つの規程が，前節の条件を満たすように表現できます．
- $i$ が $j$ の約数であるような$i$, $j$ に対し，「$p_i$ が成立して $p_j$ が成立しない」とき，$\infty$ 支払う．
- $a_i > 0$ なる $i$ について，「$p_i$が成り立たない」とき，$a_i$ 受け取る
- $a_i < 0$ なる $i$ について，「$p_i$が成り立つ」とき，$-a_i$ 支払う
FoxAndGo3
診断人さんのスライド 36～54 でとり上げられている問題です．そこでは，うまくいくグラフと，そうでないグラフが説明されています．
$P_0$を，次の命題全体とします．
- $p_{ij}$ ... 位置 $(i, j)$ に黒を置く
- $q_{ij}$ ... 位置 $(i, j)$ の白を取り除く
すると，次のように条件が書けます．
- 何も置かれていない位置 $(i, j)$ について，
- $p_{ij}$が成り立つとき1支払う
- $p_{ij}$が成り立たないとき1受け取る
- 白石が置かれている位置 $(i, j)$ について，
- $q_{ij}$が成り立つとき1受け取る
- $(i,j)$ の隣接4点 (この問題では，隣接4点には白はないと仮定されている) のうち，何も置かれていない点 $(x, y)$ について，$q_{ij}$が成立して $p_{xy}$が成立しなければ，$\infty$ 支払う．
これでうまく表現できました．注意すべき点としては，$P_0$ を次のように定めたのではうまくいかない，ということがあります．
- $p_{ij}$ ... 位置 $(i, j)$ に黒を置く
- $q'_{ij}$ ... 位置 $(i, j)$ の白を置いたままにする．
こうしますと，最後の規程に現れる条件が，「$q'_{ij}$と$p_{xy}$がともに成立しないならば」となってしまいます．これは，受取りの条件としては正当ですが，支払の条件に使うことはできません．
グラフの構成
まず，問題を言い換えて，受取りに関する規定「条件Aが成り立てばB受取る」を，「条件Aが成り立たなければ，B支払う」に変更します．あらかじめ B を受取っておいてこの新たな規程を適用するのと，もとの問題は同じ事になります．したがって，言い換えた後の問題を解いて，結果に Bを加えれば良いです．ここで，受取りの条件が満たすべき形の否定を作ると，支払の条件が満たすべき形になっていることに注意してください．
グラフを構成します．まず，$P_0$ の各要素に対応するノードを作ります．つぎに，各支払規程を見ます．条件は，$Q$ と $R$ を使って表されています．支払額を$C$とします．
- 新しいノード $u$ と $v$ を作る．
- $Q$ の各要素に対応するノードから，$u$ へ，容量$\infty$の辺を張る．
- $v$ から $R$ の各要素に対応するノードへ，容量$\infty$の辺を張る．
- $u$ から $v$ へ，容量$C$の辺を張る．
ただし，$Q$ や $R$ が単元集合の時には，$u$ や $v$ を作るのを省略して，その単元自身を用いるものとします．
ノードTrueとFalseの最小カットが，もとめる最小値になっています．
正当性
以下の2つを示します．
- $P_0$への任意の真偽値割り当てに対し，その時の支払額が最小カット以上であること
- 支払額が，最小カットと等しくなるような$P_0$の真偽値割り当てがあること
まず，1.です．ノードは，$P_0$ の要素に対応しているか，または，規程の条件 $Q$, $R$ に対応しているかのいずれかです．ノードの集合$U$ を，つぎのノードの全体と定義します．
- ノードが$P_0$の要素に対応しているときには，その対応している要素に真が割り当てられている
- $Q$に対応しているときには，$Q$の要素の少なくともひとつに真が割り当てられている
- $R$に対応しているときには，$R$の要素のすべてに真が割り当てられている
$V$ は，$U$ に属さないノードの全体とします．すると，$(U, V)$ は，True-False カットであり，支払額がこのカットの値となることが確認できます．
次に2.です．最小カット$(U_0, V_0)$ をとり，$P_0$ に対する真偽値割り当てとして，$p \in P_0$ に対応するノードが $U_0$ に属しているときに真，そうでないときに偽とするものを取ります．このときの支払額 $C'$ がカットの値 $C_0$ と一致することを言います．帰謬法で，$C_0 \neq C'$ としましょう．1.より，$C_0 < C'$ です．特に $C_0 < \infty$ です．すると，規程に現れる$Q$と$R$の組で，$Q$がすべて偽で，$R$がすべて真になっているものであって，この$Q$と$R$に対応するノード$s$と$t$について，$s \in U_0$, $t \in V_0$ となるものが存在しなければなりません．なぜなら，そのようなものが無いとすると，グラフ上の有限容量の辺でカットの値に寄与できるものは，$Q$ のうち一つ以上が真で，$R$のうち一つ以上が偽のものだけですが，そのようなものを全部集めても $C'$ しかないからです．さてこの場合，カット $(U_0 - \{s\}, V_0 \cup \{s\})$ を考えると，カット $(U_0, V_0)$ よりも真に値が小さくなってしまいます．矛盾が導かれました．
適用例．その2
The Year of Code Jam
診断人さんのスライド 56～68 でとりあげられている問題です．
今度は，次の命題を考えてもうまくいきません:
- $p_d$ ... 日付 $d$ のマスを青にする．
条件を書くと，次のようになってしまいます．
- 「?」が書かれている日付 $d$ に対し，「$p_d$が成立すれば，4受け取る」
- 隣接する日付の組 $(d, e)$ に対し，「$p_d$が成立し，$p_e$も成立すれば 2 支払う」
前者は適用可能な条件ですが，後者はそうではありません．
そこで，診断人さんのスライドにあるのと同じ工夫をすることになります．命題を次のようにします．
- $p_d$ ... 日付 $d$ が奇数マスかつ青であるか，偶数マスかつ白であるかのいずれかである．
この言い換えによって，条件は以下のようになります．
- 「?」が書かれている奇数マス日付$d$について，「$p_d$が成立すれば，4受け取る」
- 「?」が書かれている偶数マス日付$d$について，「$p_d$が成立しなければ，4受け取る」
- 隣接する日付の組 $(d, e)$ に対し，「$p_d$が成立し，$p_e$が成立しなければ 2 支払う．」(ただし，奇数マスに入っている方を$d$とする)
これで問題が最小カットに帰着できました．
Surrounding Game
診断人さんのスライド70～84です．
マス$v$に隣接するマスの集合を $N(v)$ と書きます．命題をまず次のように考えてみます．
- $p_v$ ... マス$v$に石を置く．
すると，条件は以下のようになります．
- $b_v - c_v > 0$のとき，$p_v$ が成り立てば，$b_v - c_v$ 受け取る．
- $b_v - c_v < 0$のとき，$p_v$ が成り立てば，$c_v - b_v$ 支払う．
- $p_v$ が成り立たず，すべての $w \in N(v)$ に対して $p_w$ が成り立つならば，$b_v$ 受け取る．
3番目の条件は，前節に書いた形と似ているようにも見えますが，残念ながら，肯定と否定が混じっています．さきほどの The Year of Code Jam と同じように，奇数マスと偶数マスでyes/noを入れ換えればうまくいきます．
- $p_v$ ... $v$が奇数マスでありかつ石を置かれているか，または，$v$が偶数マスでありかつ石が置かれていない．
条件を書き直します．
- $b_v - c_v > 0$となる奇数マス$v$について，$p_v$ が成り立てば，$b_v - c_v$ 受け取る．
- $b_v - c_v > 0$となる偶数マス$v$について，$p_v$ が成り立たなければ，$b_v - c_v$ 受け取る．
- $b_v - c_v < 0$となる奇数マス$v$について，$p_v$ が成り立てば，$c_v - b_v$ 支払う．
- $b_v - c_v < 0$となる偶数マス$v$について，$p_v$ が成り立たなければ，$c_v - b_v$ 支払う．
- 奇数マス$v$ について，すべての $w \in \{v\} \cup N(v)$ に対して $p_w$ が成り立つならば，$b_v$ 受け取る．
- 偶数マス$v$ について，すべての $w \in \{v\} \cup N(v)$ に対して $p_w$ が不成立ならば，$b_v$ 受け取る．
前節の形になりましたので，最小カットに帰着できます．