単純な最小カットで表現できる条件

変数 への の割り当てに対してコストが以下の図のようになるとします。

コストを最小化するとき、 ならば最小カットで表現できます。

説明

最小カットで使えるプリミティブな操作を考えます

また、解に直接値を加えることで全体に することが出来ます。
量 を考えると、 の辺で減少し、それ以外では変化しません。 よってこれらの辺で表現できる必要条件 が得られます。 一方これが実際に構築可能であることもすぐに示せます。

変数の反転

一方の変数を反転することを考えると不等号が逆のものが表現できます。 よってそのままでは表現できなくても、変数をいくらか反転すると表現可能となる可能性があります。

• 
  の反転は一致する必要があります
  
• 
  反転の有無に関係なく表現可能です
  
• 
  の反転が異なる必要があります
  

yukicoder 957 植林

行と列が変数です。その列/行一帯を植林することを とします。 すると 2 変数が関わり合う部分のコストは以下のようになります。

行か列のいずれかを植えることにしたらそのマスは費用を払う必要がある、という意味です。 これは を満たすことが から分かり、表現可能です。