概要
問題文中の $E$ の数式
${W\times H}$ は $1$ 元集合なので、何か変なお気持ち記法になっているように思います。適当に正しくしておきます。
- $V = {(x,y)\mid 1\leq x\leq h, 1\leq y\leq w}$ とする（マス目の全体）。
- $v\in V$ に対してその「$4$ 近傍」を $d(x,y) = {(x’, y’)\in V\mid |x-x’|+|y-y’|=1}$ と定める。「$4$ 近傍」と言ってはいるが、$3$ 元以下の集合になる場合もある。
- $E = \sum_{(x,y)\in V} \lambda|X(x,y) – Y(x,y)| + \sum_{(x,y)\in V}\sum_{(nx,ny)\in d(x,y)} \frac{\kappa}{2}|X(x,y)-X(nx,ny)|$ と定める。
解法
最小カットを利用する基本的な問題です。
- super node $S$, $T$ を用意する。$V\amalg \{S,T\}$ を頂点集合とするネットワークを考える。
- カット とは、頂点集合の $S$ 側・ $T$ 側への分割である。マス $v\in V$ を黒く塗ることを「$S$ 側に含めること」、白く塗ることを「$T$ 側に含めること」と見なして、カットの値が $E$ に等しくなるようにネットワークを定めます。
具体的には次のようにします。
- $Y(v)$ が黒であれば、$S\text{-}v$ 間に容量 $\lambda$ の辺を張る。これで、「$Y(v)$ が黒で $X(v)$ が白ならば $\lambda$ の減点」が表現できる。
- $Y(v)$ が白であれば、$v\text{-}T$ 間に容量 $\lambda$ の辺を張る。上と合わせて、$|X(v)-Y(v)|$ の部分が表現できた。
- $v, w$ が隣接する $2$ 頂点であるとする。$v\text{-}w$ 間および $w\text{-}v$ 間の両方に容量 $\kappa$ の辺を張る。前者の辺が、「$X(v)$ が黒で $X(w)$ が白」の場合の減点を表し，後者の辺が「$X(w)$ が黒で $X(v)$ が白」の場合の減点を表す。合わせて $|X(v)-X(w)|$ の寄与を表現できている。
同じ $(v,w)$ は $E$ において $2$ 回数えられており、容量は $\kappa$ で良いことに注意しましょう。また、「$4$ 近傍」の外周における定義を冒頭で述べたものであることも関係しています。
あとは適当な最大流アルゴリズムを使って、最小カットを求めればよいです。
