燃やす埋める問題 - ferinの競プロ帳

燃やす埋める問題は以下の問題である

頂点を赤と青に塗り分ける
塗り方の依存関係によってスコアが変動する
(例) 頂点 $x$ が赤で頂点 $y$ が青に割り当てられたとき $z \geq 0$ 失う
スコアの和の最小化を行え

この問題は最小カットに帰着して解くことができる

必ず赤が割り当てられる頂点 $S$ ，必ず青が割り当てられる頂点 $T$ を用意
頂点 $S$ から頂点 $T$ への最小カットを求める
スコアが変動する条件によって辺を張る

辺の張り方

頂点 $x$ が赤で頂点 $y$ が青ならば $z \geq 0$ 失う

このとき「頂点 $x$ から頂点 $y$ に容量 $z$ の辺」を張ればよいことを基本とする

頂点 $x$ を赤で塗ると $z \geq 0$ 失う

頂点 $x$ が赤で頂点 $T$ が青ならば $z \geq 0$ 失うと言い換えられる
頂点 $x$ から頂点 $T$ に容量 $z$ の辺を張る

頂点 $x$ を青で塗ると $z \geq 0$ 失う

頂点 $S$ が赤で頂点 $x$ が青ならば $z \geq 0$ 失うと言い換えられる
頂点 $S$ から頂点 $x$ に容量 $z$ の辺を張る

頂点 $x$ を赤で塗ると $z \geq 0$ 得る

無条件に $z$ 得る
(頂点 $S$ が赤で) 頂点 $x$ が青ならば $z \geq 0$ 失うと言い換えられる．
無条件に $z$ 得る
頂点 $S$ から頂点 $x$ に容量 $z$ の辺を張る

頂点 $x$ を青で塗ると $z \geq 0$ 得る

無条件に $z$ 得る
頂点 $x$ が赤で (頂点 $T$ が青) ならば $z \geq 0$ 失うと言い換えられる．
無条件に $z$ 得る
頂点 $x$ から頂点 $T$ に容量 $z$ の辺を張る

頂点 $x$ が赤で頂点 $y$ が赤ならば $z \geq 0$ 得る

新たな頂点 $w$ を用意し

無条件に $z$ 得る
頂点 $w$ が青だと $z$ 失う
頂点 $w$ が赤ならば，必ず頂点 $x$ は赤
頂点 $w$ が赤ならば，必ず頂点 $y$ は赤

と帰着する．「必ず頂点 $x$ は赤」は「頂点 $x$ が青ならば $\infty$ 失う」と言い換えられる

無条件に $z$ 得る
頂点 $S$ から頂点 $w$ に容量 $z$ の辺を張る
頂点 $w$ から頂点 $x$ に容量 $\infty$ の辺を張る
頂点 $w$ から頂点 $y$ に容量 $\infty$ の辺を張る

頂点 $x$ が青で頂点 $y$ が青ならば $z \geq 0$ 得る

赤の場合と同様に，新たな頂点 $w$ を用意し

無条件に $z$ 得る
頂点 $w$ が赤だと $z$ 失う
頂点 $w$ が青ならば，必ず頂点 $x$ は青
頂点 $w$ が青ならば，必ず頂点 $y$ は青

と帰着する．「必ず頂点 $x$ は青」は「頂点 $x$ が赤ならば $\infty$ 失う」と言い換えられる

無条件に $z$ 得る
頂点 $w$ から頂点 $T$ に容量 $z$ の辺を張る
頂点 $x$ から頂点 $w$ に容量 $\infty$ の辺を張る
頂点 $y$ から頂点 $w$ に容量 $\infty$ の辺を張る

頂点 $x$ が赤で頂点 $y$ が赤ならば $z \geq 0$ 失う

基本的には難しいがグラフが二部グラフの性質から可能なこともある．辺の順序を入れ替え，「頂点 $x$ が赤で頂点 $y$ が青ならば $z$ 失う」のように辺を張ればよい．グラフの張り方については問題例のイルミネーションにも書いた．
(参考) 最小カットを使って「燃やす埋める問題」を解く by shindanninさんのp55，蟻本p359

頂点 $x$ が赤で頂点 $y$ が青ならば $z \geq 0$ 得る

新たな頂点 $w$ を用意し

無条件に $z$ 得る
頂点 $w$ が赤ならば $z$ 失う
頂点 $w$ が青ならば頂点 $x$ は赤
頂点 $w$ が青ならば頂点 $y$ は青

と帰着する．頂点 $w$ が青ならば頂点 $x$ は赤 $\iff$ 頂点 $w$ が青，頂点 $x$ が青ならば $\infty$ 失うとなるが前述したようにこれは二部グラフでないと厳しい．以下の画像のように辺を張ると， $x$ が青もしくは $y$ が赤のとき $w$ への辺が残っているので $z$ の辺を切らなければならない．

f:id:ferin_tech:20191028182209p:plain

以下に各状況においてどのような辺を張るべきかまとめる

依存関係	グラフの辺の張り方
$x$ が赤のとき $z$ 失う	$x$ から $T$ へ容量 $z$
$x$ が赤のとき $z$ 得る	「無条件で $z$ 得る」「 $S$ から $x$ へ容量 $z$ 」
$x$ が青のとき $z$ 失う	$S$ から $x$ へ容量 $z$
$x$ が青のとき $z$ 得る	「無条件で $z$ 得る」「 $x$ から $T$ へ容量 $z$ 」
$x$ が赤で $y$ が青なら $z$ 失う	$x$ から $y$ へ容量 $z$
$x$ が赤で $y$ が赤なら $z$ 得る	「無条件に $z$ 得る」「頂点 $S$ から頂点 $w$ に容量 $z$ の辺を張る」「頂点 $w$ から頂点 $x$ に容量 $\infty$ の辺を張る」「頂点 $w$ から頂点 $y$ に容量 $\infty$ の辺を張る」
$x$ が青で $y$ が青なら $z$ 得る	「無条件に $z$ 得る」「頂点 $w$ から頂点 $T$ に容量 $z$ の辺を張る」「頂点 $x$ から頂点 $w$ に容量 $\infty$ の辺を張る」「頂点 $y$ から頂点 $w$ に容量 $\infty$ の辺を張る」
頂点 $x$ が赤で頂点 $y$ が赤ならば $z$ 失う	二部グラフなら辺の順序入れ替えで帰着
頂点 $x$ が青で頂点 $y$ が青ならば $z$ 失う	二部グラフなら辺の順序入れ替えで帰着

(参考)

project selection problem

3状態に割り振るタイプの問題

KUPC2019 H - 123パズルのように各頂点を3状態に割り振るタイプの問題について考える．自分で考えたことが含まれるので間違ってるかも．

頂点 $u$ に $A_u (1 \leq A_u \leq 3)$ を割り振るとする．以下のグラフで辺 $(S,u), (u,u'), (u',T)$ をそれぞれ $A_u=1,2,3$ を表すとする．
$x \to y$ に容量 $\infty$ の辺を張っておく．これによってS-Tカットで $x$ が $S$ 側ならば $y$ も $S$ 側に含まれる制約を表せる．

f:id:ferin_tech:20191028182143j:plain

$(A_u, A_v)=(x, y)$ だと $C_{xy}$ 失う

KUPC2019 H - 123パズルの解説を一般化できないかと思い考えたもの頂点 $p$ から頂点 $q$ に容量 $c$ の辺を張る．S-Tカットで頂点 $p$ は $S$ 側，頂点 $q$ は $T$ 側に含まれる場合，この辺を切らなければならない．この辺を切らなければならないS-Tカットに相当する $(A_u,A_v)$ について $c$ 失う制約条件を表すことができる．
以下の組合せで表現できる $C_{xy}$ ならグラフで表わせる

$S \to u$ に容量 $c$ の辺を張る

S-Tカットが以下のときこの辺を切らなければならない

$({S},{u,u',v,v',T})$ $(A_u,A_v)=(1,1)$ に相当
$({S,v},{u,u',v',T})$ $(A_u,A_v)=(1,2)$ に相当
$({S,v,v'},{u,u',T})$ $(A_u,A_v)=(1,3)$ に相当

$(A_u,A_v)$ が $(1,1),(1,2),(1,3)$ のいずれかの場合 $c$ 失う

$S \to u'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)$ のいずれか

$S \to v$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,1),(2,1),(3,1)$ のいずれか

$S \to v'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,1),(2,1),(3,1),(1,2),(2,2),(3,2)$ のいずれか

$S \to T$ に容量 $c$ の辺を張る

任意の $(A_u,A_v)$

$u \to u'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(2,1),(2,2),(2,3)$ のいずれか

$u \to v$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(2,1),(3,1)$ のいずれか

$u \to v'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(2,1),(3,1),(2,2),(3,2)$ のいずれか

$u \to T$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)$ のいずれか

$u' \to v$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(3,1)$

$u' \to v'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(3,1),(3,2)$ のいずれか

$u' \to T$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(3,1),(3,2),(3,3)$ のいずれか

$v \to v'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,2),(2,2),(3,2)$ のいずれか

$v \to u$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,2),(1,3)$

$v \to u'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,2),(1,3),(2,2),(2,3)$ のいずれか

$v \to T$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,2),(2,2),(3,2),(1,3),(2,3),(3,3)$ のいずれか

$v' \to u$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,3)$

$v' \to u'$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,3),(2,3)$ のいずれか

$v' \to T$ に容量 $c$ の辺を張る

$(A_u,A_v)$ が $(1,3),(2,3),(3,3)$ のいずれか

一様加算できる領域は縦横1列と右上，左下のあたり
f:id:ferin_tech:20191028182115p:plain

可能な $C_{xy}$ についてシンプルな形で表現できるのかはよくわからなかったが，左下・右上にあるものほど失うスコアが大きいならばつくれそう．

Project Selection (燃やす埋める) 周りの話についてもう少し考えた by とこはるさんに

集合の切り分け方が部分集合関係の鎖になっていることが本質的な気がしてきます。

という視点が書いてあった

$A_u=x$ だと $c$ 失う

「任意の $A_v$ について $A_u=x$ だと $c$ 失う」に対応する辺はあるのでこれは表現できる．
$A_u=1$ なら $S \to u$ ， $A_u=2$ なら $u \to u'$ ， $A_u=3$ なら $u' \to T$ の辺を張ればよい．

$A_u=x$ だと $c$ 得る

燃やす埋めると同様に変形を行う．
無条件で $c$ 得られるとして $A_u \neq c$ ならば $c$ 失うとすればいい．

$A_u \neq 1$ ならば $u \to u'$ と $u' \to T$ の辺
$A_u \neq 2$ ならば $S \to u$ と $u' \to T$ の辺
$A_u \neq 3$ ならば $S \to u$ と $u \to u'$ の辺

----- ToDo -----
$(A_u,A_v)=(x,y)$ だと $c$ 得るは表現できる？
$(A_u,A_v)=(x,y)$ 以外の領域全てに加算できるのならつくれそう
これ以外の表現方法ある？
----- ToDo -----

問題例

ARC085 E - MUL

頂点を割らない( $=S$ 側)，割る( $=T$ 側)の2種類に分割する問題と考える

$x$ が割られていた場合， $x$ の倍数は割られていなければならない．これは $x$ の倍数が割られていて， $x$ が割られていない状況を禁止( $\infty$ 失う)とすればよい．グラフでは $x$ の倍数から $x$ へ容量 $\infty$ の辺を張ることに相当する．
$a_i \lt 0$ のとき，頂点 $i$ を割らなければ $a_i$ 失う．グラフでは $S$ から $i$ へ容量 $a_i$ の辺を張ることに相当する．
$a_i \geq 0$ のとき，頂点 $i$ を割らなければ $a_i$ 得る．グラフでは，「無条件で $a_i$ 得る」「 $S$ から $i$ に容量 $a_i$ の辺を張る」ことに相当する．

(無条件で得た分) - (このグラフの最小カット) が答えとなる．

https://atcoder.jp/contests/arc085/submissions/8072769

RUPC2019day2 H - Ghost

幽霊 $i$ が左を向いている( $=S$ 側)，右を向いている( $=T$ 側) の2種類に分割すると考える

以下の制約を組み込んだグラフをつくれればよい

幽霊 $i$ が元々向いていた方と反対側になった場合 $A_i$ 失う
$S_i$ が右， $T_i$ が左を向いていたら $B_i$ 失う ( $S_i \lt T_i$ となるようにする)

これは燃やす埋めるで表せるのでグラフを構成して最小カットを求めることで答えがわかる．

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3943637

ACPC2018day1 H - 板

writer解説各マスについて行える操作を横向き( $=S$ 側)か縦向き( $=T$ 側)の $1\times 1$ の板を置ける操作だと考える．
穴があるマスに横向き/縦向きの板を置くと1失う．グラフでは $S$ から各マスへ容量 $1$ ，各マスから $T$ へ容量 $1$ の辺を張ることに相当する．
穴があるマス $(i,j)$ と $(i,j+1)$ が両方横向きならば1得る．同様に，穴があるマス $(i,j)$ と $(i+1,j)$ が両方縦向きならば1得る．これは頂点 $x,y$ が両方赤/青のとき $z$ 得る制約に相当し，グラフで表現できる．
グラフの最小カット - 無条件で得た分が答えになる．

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3943257#1

CPSCO2019 Session2 F - Treasure Collector

マスに着目すると，横/縦に移動するロボットでコインを取るの2択に振り分ける問題だと考える．板と同じように，マスにロボットを置くと1失い，横(縦)に隣接したマスが横(縦)につながってると1得ると考える．板と違う点として $A_i$ ごとにコストがかかるのでロボットの初期位置との距離が $\text{mod } A_i$ で $1$ のとき以外，この1得る制約がかかる．
ロボットを置くと1失う部分については $n(n-1)$ で固定である．それ以外については以下の制約を反映したグラフの最小カットが答えになる．

横(縦)に隣接したマスが横(縦)につながってると1得る
1つのマスを複数のロボットが踏むことを禁止

https://atcoder.jp/contests/cpsco2019-s2/submissions/8107311

RUPC2019day1 G - イルミネーション

装置をon → 周りの電球の $\sum b_{ij} - W$ の分スコアが変化
装置をoff → 変化なし $(\pm 0)$
電球 $(i,j)$ を共有している装置 $p,q$ が両方on → $b_{ij}$ 失う

最小カットを求めるグラフでの頂点番号を左上の装置から順番に $0,1,\ldots,n$ とする．
f:id:ferin_tech:20191028182005j:plain

装置のon, offについての辺のみを張ったグラフをサンプルでつくったグラフが下の画像の左のグラフになっている．電球を共有している装置の分の辺を張りたいが，「頂点 $x,y$ が両方赤のとき $z$ 失う」制約条件に該当するので基本的に難しい．
頂点 $x,y$ について，どちらも　 $S \to x$ の辺をカットするときに対する制約であることが問題となる．そこで，一部の頂点について $S \to x$ と $x \to T$ の辺の容量を逆にすることで，「頂点 $x,y$ の色が異なるときに $z$ 失う」条件に帰着する．
この容量の交換は一般にできるわけではないが， $x,y$ をつないだグラフが二部グラフであれば可能で，今回の問題はグリッドグラフなので二部グラフである．
サンプルで容量を交換し，電球を共有している装置の分の辺を張ったグラフが下の画像の右になっている．
f:id:ferin_tech:20191028182041j:plain

このグラフで最小カットを求めればよい．
https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day1/3943618

yukicoder No.119 旅行のツアーの問題

各国について2つの頂点を作成し， $S-(n$ 頂点 $)-(n$ 頂点 $)-T$ のようなグラフをつくる．各国について3辺が存在するので，これらが「行かない」「行くけど参加しない」「参加する」の3種類のどれかになるように割り当てる．
$D_i$ で「参加する」， $E_i$ で「行くけど参加しない」を選ぶのを禁止したいので $\infty$ 失うとしたい．コスト $C_{xy}$ のうち左下，右上が大きくなるようにできればグラフで表現できる．「行くけど参加しない」「行かない」「参加する」の順番で辺を割り当てることで， $D_i$ の右側頂点から $E_i$ の左側頂点に容量 $\infty$ の辺を張ればよい．
このグラフで最小カットを求めれば答えがわかる．

https://yukicoder.me/submissions/392293

KUPC2017 H - Make a Potion

燃やす埋めるかは微妙な気がするが， $i$ 番目の液体を何リットル使うか？に振り分ける + 依存関係が存在なのでグラフの作り方の要領は同じ．

「 $a_i$ 番目の液体を体積 $x_i$ 以上使うなら $b_i$ 番目の液体を体積 $y_i$ 以上使う」の制約がある場合， $a_i$ 番目の液体を $z \lt x_i-1$ のような中途半端な量を使うことが最適にはなりえない．使う量の候補は

$a_i$ 番目を体積 $x_i - 1$
$a_i$ 番目を体積 $x_i$
$b_i$ 番目を体積 $y_i$
$i$ 番目を体積 $v_i$

となる． $i$ 番目を体積 $j$ 使う場合に得る/失うコストに応じた辺と $M$ 個の条件について禁止する( $\infty$ 失う)に応じた辺を張ったグラフで最小カットを求めればよい．

https://atcoder.jp/contests/kupc2017/submissions/8098901

3種類以上に振り分けるときのグラフの構築
$x \to y$ の容量 $z$ の辺を切るのは，S-Tカットで $x$ が $S$ 側， $y$ が $T$ 側にあるときである．この辺はS-Tカットがこの状況ならば $z$ 失うという制約条件に対応する．
ある条件のとき $z$ 得るを表現したい場合は「無条件で $z$ 得る」「ある条件以外の場合 $z$ 失う」とすると失う場合に帰着できる．
条件 $X$ のときに条件 $Y$ を禁止する → 条件 $X$ を頂点 $x$ から終点 $T$ ，条件 $Y$ を始点 $S$ から頂点 $y$ に対応させる． $x \to y$ に容量 $\infty$ の辺を張る．この辺を張れるように選択肢を並べる．

辺の張り方

頂点 が赤で頂点 が青ならば 失う

頂点を赤で塗ると失う

頂点を青で塗ると失う

頂点を赤で塗ると得る

頂点を青で塗ると得る

頂点 が赤で頂点 が赤ならば 得る

頂点 が青で頂点 が青ならば 得る

頂点 が赤で頂点 が赤ならば 失う

頂点 が赤で頂点 が青ならば 得る

3状態に割り振るタイプの問題

だと 失う

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

に容量 の辺を張る

だと 失う

だと 得る

問題例

頂点 $x$ が赤で頂点 $y$ が青ならば $z \geq 0$ 失う

頂点 $x$ を赤で塗ると $z \geq 0$ 失う

頂点 $x$ を青で塗ると $z \geq 0$ 失う

頂点 $x$ を赤で塗ると $z \geq 0$ 得る

頂点 $x$ を青で塗ると $z \geq 0$ 得る

頂点 $x$ が赤で頂点 $y$ が赤ならば $z \geq 0$ 得る

頂点 $x$ が青で頂点 $y$ が青ならば $z \geq 0$ 得る

頂点 $x$ が赤で頂点 $y$ が赤ならば $z \geq 0$ 失う

頂点 $x$ が赤で頂点 $y$ が青ならば $z \geq 0$ 得る

$(A_u, A_v)=(x, y)$ だと $C_{xy}$ 失う

$S \to u$ に容量 $c$ の辺を張る

$S \to u'$ に容量 $c$ の辺を張る

$S \to v$ に容量 $c$ の辺を張る

$S \to v'$ に容量 $c$ の辺を張る

$S \to T$ に容量 $c$ の辺を張る

$u \to u'$ に容量 $c$ の辺を張る

$u \to v$ に容量 $c$ の辺を張る

$u \to v'$ に容量 $c$ の辺を張る

$u \to T$ に容量 $c$ の辺を張る

$u' \to v$ に容量 $c$ の辺を張る

$u' \to v'$ に容量 $c$ の辺を張る

$u' \to T$ に容量 $c$ の辺を張る

$v \to v'$ に容量 $c$ の辺を張る

$v \to u$ に容量 $c$ の辺を張る

$v \to u'$ に容量 $c$ の辺を張る

$v \to T$ に容量 $c$ の辺を張る

$v' \to u$ に容量 $c$ の辺を張る

$v' \to u'$ に容量 $c$ の辺を張る

$v' \to T$ に容量 $c$ の辺を張る

$A_u=x$ だと $c$ 失う

$A_u=x$ だと $c$ 得る