最小カット
S-T最小カット
頂点Sが赤、頂点Tが青で塗られている（残りの頂点は色が塗られていない）、辺に重みのついた有向グラフが与えられる
この時、各頂点を赤か青に塗る塗り方であって、赤から青へ向かう辺重みの合計が一番小さくなるようなもののことを S-T最小カット と呼ぶ*1
重みが非負の時最小カットはSからTの最大流と等しいと言う性質があるので、最大流のアルゴリズムを用いて多項式時間で解ける
（上の図を見ると赤全体から青全体に流せる量が11以下なのは明らか（∴最大流最小カット）で、逆もちょっと考えると分かる）
（最大流で出てくるのは最小カットの重みだけであるが、もうちょっと考えるとそこから塗り方は復元出来る）
なので問題を最小カットに帰着出来ると嬉しい
帰着出来る問題例
Optimal Closure in a Digraph*2
たくさんの仕事があり、それぞれ実行した時の利益が分かっている
仕事には負の利益を持つものも存在し、いくつかの仕事については「仕事 を行う場合必ず仕事
も行う必要がある」のような関係があるとする
このような時、利益を最大にする為に実行すべき仕事の集合を求めよ
まず自然に以下のような有向グラフが考えられる
各頂点が仕事に対応し、利益が重みとしてついている
また、「 を行うには
も行う必要がある」時、
から
に辺が張られている
こうすると解きたい問題は、行う仕事を赤で、行わない仕事を青で塗ると解釈すると、
「赤から青への辺が存在しないような頂点の塗り方で、赤の頂点の重みの総和が最大となるものを求めよ」
と言い換えることができる
いかにも最小カットっぽいので、グラフを辺重みのものに作り変えて最小カットに帰着させる
まず、「赤から青への辺が存在しない」と言う条件であるが、これは元の有向グラフの辺に無限の重みをつけてやれば良い
最小カットはなるべく赤から青への辺重みが小さくなる塗り方をするので、条件が自然と満たされるようになる
「仕事を行うと利益 を得る」と言う条件は、
の正負で場合分けをする
ここで大事なのは「利益の最大化」ではなく「損失の最小化」をすると言い換えることである（最小カットは最小化しか出来ない為）
v>0
仕事を行うと利益 を獲得すると言うのは、もともと利益
を獲得しており仕事を行わない（頂点を青く塗る）と損害
を被ると言い換えられるから、以下の二つの操作を行えば良い
- 元々獲得していたと見做す利益を数えるカウンタに
を足す
から重み
v<0
仕事を行う（頂点を赤く塗る）と損害 が発生するのだから
に重み
の辺を張る
求めるのはこのグラフの最小カットの値をカウンタの値から引いたものである
類題:
https://atcoder.jp/contests/typical90/tasks/typical90_an
燃やす埋める？
もっと広い範囲を燃やす埋めるって呼んでる人もいるけど取り敢えず二部グラフについてだけ
いままでは各辺が「赤から青になった時のみ発生する重み」を持っていて、その重みを最小化する問題だった
これが同色の時のみ発生する重みの最小化みたいな問題になると難しいんだけど、グラフが二部グラフだったら片側の色を反転させると最小カットに帰着出来るんじゃ無いかみたいな話
嘘かも、一次資料を見てくれ
[http: //
: title]