目次
燃やす埋める問題
競技プログラミングにおける、以下のようなパターンの問題の総称。
問題設定(例題)
$a_1,a_2,...,a_N$ の $N$ 個の廃棄物がある。全て燃やすか埋めるかして処分する。それぞれにコストがかかる。
| $a_1$ | $a_2$ | … | $a_N$ | |
|---|---|---|---|---|
| 燃やすコスト | 50 | 60 | … | 130 |
| 埋めるコスト | 100 | 120 | … | 90 |
さらに「$a_1$ を燃やして $a_2$ を埋めると罰金100円」など、2つの処分方法の組合せによる追加条件がいくつかある。
かかるコストを最小化せよ。
類似概念
近い概念に、PSP（Project Selection Problem）というのがある。
また、QUBO（Quadratic Unconstrained Binary Optimization、制約なし二次形式二値変数最適化）というのもある。
どれも「一番シンプルな問題設定」といったら上のような例題になるけど、どの辺まで応用された問題を扱うかが微妙に異なるっぽい（あまり詳しくないけど）。
まぁ「燃やす埋める問題」は競プロ界隈のローカルネームであり、より一般化された/応用的な内容を学んでいきたい場合は上の名前で調べていけばいいと思う。
ただ、最初の取っかかりとして興味をそそられる名前だし思い出しやすいのでこれはこれでいいと思う。
解き方
追加条件が無ければ単純に $a_1 ... a_N$ についてコストの安い方を選べば良いだけだが、 追加条件があるためにあちらを立てればこちらが立たずで手に負えなくなる。
与えられた条件をグラフで上手く表すことで、最小カット問題として表現することができる。
ただし、追加条件次第で解けないことがある。この解法で解ける条件と解けない条件は後述する。
グラフ化
カットの定義
グラフの「カット」とは、グラフの各頂点（廃棄物）を2つのグループ $S$（燃やす）と $T$（埋める）に振り分けること。
そしてカットのコストとは、$(Sに属する頂点)→(Tに属する頂点)$ に張られている辺のコストの合計のことを指す。
全ての頂点を $S$ や $T$ にすると自明にカットコストが0になってしまうので、 通常、必ず $S$ の頂点 $s$ と必ず $T$ の頂点 $t$ を決めるか、仮想的に追加する。
s -- 10 -→○-- 20 -→○ 30｜ ↑ 50｜ こんなグラフがあったとして ↓ 40｜ ↓ ○-- 60 -→○-- 70 -→ t s -- 10 →[T]-- 20 →[S] 30｜ ↑ 50｜ こう分けた場合、カットのコストは ↓ 40｜ ↓ 10 + 40 + 50 + 70 = 170 [S]-- 60 →[S]-- 70 -→ t
この定義の中で、元の問題を、カットのコストを最小化する問題に上手く落とし込めるよう、グラフを構築していく。
燃やす・埋める単独のコスト
まず、追加条件の無い、単独の燃やすコストと埋めるコストだけを考えると、以下のようなグラフになる。
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やすコスト | 50 | 60 | 130 |
| 埋めるコスト | 100 | 100 | 100 |
,-- 100-→ a1 --- 50---,
燃 | ↓ 埋
や s - 100-→ a2 --- 60-→ t め
す | ↑ る
`-- 100-→ a3 -- 130---'
$a_1$ を燃やすコスト50が、$s$ から遠い右の辺のコストになっているのが少し慣れが必要だが、 「$a_1$ が $S$ グループの場合にカット対象となる辺は右辺」なので、このようになる。
単にここまでの状態だと、各頂点は小さい方の辺がカット対象となるように属するグループをそれぞれ独立に選べばよい。
,-- 100-→ [S]a1 --- 50---,
燃 | ~~ ↓ 埋
や s - 100-→ [S]a2 --- 60-→ t め
す | ~~ ↑ る
`-- 100-→ [T]a3 -- 130---' 50+60+100 = 210
~~~
2つの廃棄物の組合せによるコスト
ここに「$a_2$ を燃やし $a_3$ を埋めると罰金120」という条件を追加したい。
「$a_2$ が $S$、$a_3$ が $T$ の時に120のコスト」なので、最大カットのグラフで $a_2→a_3$ の辺を追加すれば、それが表現できる。
こうすると、先ほどの $S,T$ の割り当て方では、追加した辺もカット対象となる。
,-- 100-→ [S]a1 --- 50---,
燃 | ~~ ↓ 埋
や s - 100-→ [S]a2 --- 60-→ t め
す | ｜120 ~~ ↑ る
| ↓~~~ |
`-- 100-→ [T]a3 -- 130---' 50+60+100 + 120 = 330
~~~
それなら、そもそも $a_3$ も燃やした方が安くなる。
,-- 100-→ [S]a1 --- 50---,
燃 | ~~ ↓ 埋
や s - 100-→ [S]a2 --- 60-→ t め
す | ↓120 ~~ ↑ る
`-- 100-→ [S]a3 -- 130---' 50+60+130 = 240
~~~
これが罰金を考慮した最小コストとなる。
禁止の制約
制約が「$a_2$ を燃やすと、$a_3$ を埋めてはいけない」という禁止の形になっている場合、 コストを無限大（他のコストを全て合わせても取り得ないような非常に大きな値）に設定しておくとよい。
,-- 100-→ a1 --- 50---,
燃 | ↓ 埋
や s - 100-→ a2 --- 60-→ t め
す | ↓∞ ↑ る
`-- 100-→ a3 -- 130---'
最小カットを解く
最小カットは、辺のコストを容量と見て $s→t$ 間の最大流と一致するという定理があるので、最大流問題として求められる。
表現できるコスト条件
コストが発生する条件には、最大流のグラフに落とし込めるものとできないものがある。
燃やす・埋めることに対する賞金（負のコスト）はそのままではダメ
最小カットは、結果的に最大流で解くので、負辺があると上手くいかない。（最大フロー最小カット定理）
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やす | 50 | 60 | -130 |
| 埋める | -100 | 100 | -100 |
-100は100円もらえる（負のコスト）、なんて時は、どうやって辺のコストを設定するか。
全て良い方を選んだと仮定
全て良い方の選択肢を選び、もらえるお金はもらった上で、そこからの差分を「コスト」と見なす。
たとえば $a_1$ は $100$ 円、$a_3$ は $130$ 円をあらかじめもらったと仮定。その上で差分をコストとすると、
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やす | 150 | 60 | 0 |
| 埋める | 0 | 100 | 30 |
となり、負のコストが消える。あとは、最小カットの結果から230を引いたものが本来のコストとなる。
実際の問題では、「コストを最小化せよ」でなく「得点を最大化せよ」という形で問われることも多い。
これも、「全ての得点をもらっておいた上で、達成できないということをコストにする」とコスト最小化に落とし込める。
最大値を求めるのに、最小カット問題に言い換えて、それを最大流で解く、という構造がややこしいが、 元の問題を最小カット問題に置き換える部分に注力する。
「どちらも燃やしたときに罰金」はダメ
「$a_1$ と $a_2$ を同時に燃やすと罰金」など、2つの頂点を同じグループに属させた際に正のコストが課される条件は、表現できない。 （「最大カット問題」となり、NP困難らしい）
ただし追加条件次第で、工夫すれば解ける場合がある。
意味合いを一部反転させる
$S$ を「燃やす」、$T$ を「埋める」と対応づけたのは勝手な都合であって、たとえば
- $a_1$ にとっては $S$ は燃やす、$T$ は埋めるを表す
- $a_2$ にとっては $S$ は埋める、$T$ は燃やすを表す
としても問題ない。
すると、カット対象の辺を張ることができるようになる。
,-燃- 100-→ a1 --- 50-埋-, | ↓100 ↓ a2の左右を入れ替えると、 s 埋- 60-→ a2 ---100-燃→ t 両方燃やすことに対する追加条件の辺を張れる | ↑ `-燃- 100-→ a3 -- 130-埋-'
ただ、例えばこれに加えて「$a_1$ と $a_3$ を同時に燃やすと罰金」「$a_2$ と $a_3$ を同時に埋めると罰金」という条件が重なってしまうと、 どうしてもどれかの組は同じグループに属さざるを得なくなり、カット対象の辺を張ることが不可能になる。
あくまで追加条件次第ということになる。
どういう場合にこの方法が使えるか、というと、追加条件が以下のようになる場合となる。
- 頂点全体を（カットとは別に）以下を満たすように2つの集合 $A,B$ に分けることができる
- 「$a_i$ と $a_j$ が同じグループだと正のコスト」という追加条件は、必ず $a_i,a_j$ のどちらかが $A$ でどちらかが $B$
- 「$a_i$ と $a_j$ が異なるグループだと正のコスト」という追加条件は、必ず $a_i,a_j$ はどちらも $A$ か、どちらも $B$
この場合、集合 $B$ だけ、燃やすと埋めるの意味するグループを入れ替えればよい。
まず前者の追加条件だけを見て、それぞれの $a_i,a_j$ 間に辺を張ったグラフが、二部グラフとなっていればよい。
加えて後者の追加条件もある場合は、二部グラフに分けた上で矛盾しないか調べればよい。
一例として、グリッドで、隣接するマスと同じグループならペナルティが発生するルールで得点を最大化、みたいな問題では、 隣り合うマス同士を結ぶグラフ（グリッドグラフ）は必ず二部グラフとなるので、この方法が可能となることがある。
負のコストなら可
追加条件を「$a_1$ と $a_2$ を同時に燃やすと賞金120円」とすると、可能となる。
この場合、グラフの作り方が変わってくる。追加条件も1つの頂点として表す。
- まず、無条件で120円もらったと仮定
- ダミーノード $b_1$ を追加。燃やしてもコスト0、埋めると120
- $b_1$ を燃やしたなら、必ず $a_1$ と $a_2$ も燃やす
- $b_1→a_1,a_2$ にコスト無限大の辺を追加することで表現
こうすると、グラフは以下のようになる。
,-- 100-→ a1 --- 50--, | ↑∞ ↓ s - 120-→ b1 ---- 0-→ t | ↓∞ ↑ `-- 100-→ a2 -- 60--'
$b_1$ はいわば、$S$ に属するときに「$a_1$ かつ $a_2$ を燃やす」ことを意味するノードと言える。
- $b_1$ を燃やす（$S$ にする）と、
- カット対象は0円の辺となるので、最初にもらった120円はそのまま受け取れる
- $a_1,a_2$ は $T$ にしたら無限大の辺がカット対象となってしまう
- 最小カットを求める上では無限大の辺は避けられるため、$a_1,a_2$ とも $S$ になるはず
- $b_1$ を埋める（$T$ にする）と、
- カット対象は120円の辺となるので、最初にもらった120円は没収
- $a_1,a_2$ については、制約が無くなる
- カット対象辺はあくまで $S→T$ であり、$T→S$ は含まれない
この場合は、頂点が3個以上でもよい。賞金を得るために同時に満たさなければならない頂点全てに辺を張るとよい。
- 「$a_1,a_2,a_3$ を同時に燃やすと賞金」→「$b_1$ から $a_1,a_2,a_3$ にコスト∞の辺」
また、追加条件が逆に「$a_1$ と $a_2$ を同時に埋めると賞金120円」だった場合は、辺の張り方は以下のようになる。
,-- 100-→ a1 --- 50--, 変わった点 | ↓∞ ↓ ・b1の左右が逆転 s --- 0-→ b1 -- 120-→ t ・b1と、a1,a2 間の辺の方向が逆転 | ↑∞ ↑ `-- 100-→ a2 -- 60--'
まとめ
$S=$ 燃やす を「最大流に帰着する場合の起点側」、$T=$埋める を「終点側」とする。
| 条件 | 辺の張り方 |
|---|---|
| $a_i$ を燃やすと罰金 $P$ | $a_i$ から $t$ にコスト $P$ の辺 |
| $a_i$ を埋めると罰金 $P$ | $s$ から $a_i$ にコスト $P$ の辺 |
| $a_i$ を燃やし、$a_j$ を埋めると罰金 $P$ | $a_i$ から $a_j$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も燃やすと、罰金 $P$ ※ただし$a_i,a_j$は二部グラフ上の別グループの頂点 | いずれかの選択肢を反転（$a_j$ とする） $a_i$ から $a_j$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も埋めると、罰金 $P$ ※ただし（同上） | いずれかの選択肢を反転（$a_j$ とする） $a_j$ から $a_i$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も燃やす/埋めると、罰金 $P$ ※特に二部グラフなどの特徴の無い制約 | 基本的に無理 |
| $a_i,a_j,...$ を全て燃やすと、賞金 $P$ | あらかじめ $P$ もらう ダミーノード $b$ を追加 $s→b$ にコスト $P$, $b→t$ にコスト $0$ の辺 $b$ から $a_i, a_j, ...$ にコスト $\infty$ の辺 |
| $a_i,a_j,...$ を全て埋めると、賞金 $P$ | あらかじめ $P$ もらう ダミーノード $b$ を追加 $s→b$ にコスト $0$, $b→t$ にコスト $P$ の辺 $a_i, a_j, ...$ から $b$ にコスト $\infty$ の辺 |
上に無い条件でも、他の制約次第で工夫の余地はあるようだ。（もちろんどうしても無理なものもある）
グラフ構築の考え方
グラフを構築する際、どっちからどっちの頂点へ辺を張ればよいか、混乱しやすい。
これまで、グラフ理論におけるカットの考え方から「各ノードをどちらのグループに属させるか」で考えてきた。
- ノード主体の考え方
- 全てのノードを $S$ グループ と $T$ グループ に分ける
- $u$ が $S$ に属し、$v$ が $T$ に属している場合にコストが発生する場合、$u→v$ に辺を張る
一方で、最小カット問題は「$s-t$ 間にフローが流れないように辺を切る」問題とも言えるので、 辺を主体にして「この辺を切ることが、『燃やす』を選択すること」と意味合いづけて、グラフを構築していくことも可能である。
- リンク主体の考え方
- $a_1$ を燃やして $a_2$ を埋めたらコストが発生する場合、それぞれに該当するリンクを切っても $s→t$ のフローがまだ途切れていない状態にするように辺を張る
やってることは同じでも、考え方を変えるだけで実際の問題からのグラフ構築のしやすさが異なってくる、かも。
ノード主体の場合、単独で燃やす・埋める際のコストが $s,t$ の意味合いと左右逆転するところが少し直感に反するものの、 それ以外の、追加条件の部分では、リンク主体よりも直感的に張れる気がする。
バリエーション
工夫次第でいろいろできるらしい
3択の選択肢
- 問題設定
- 「燃やす」「埋める」に、「壊す」の選択肢が追加される
- 制約条件は、「$X_i$ を燃やして $Y_i$ を埋めると罰金 $P_i$」という形式のみ（「壊す」は条件に来ない）
選択肢を増やすだけならノードを複製して横に繋ぐことも考えられるが、 これだと $S-T$ の分割や、制約条件の辺が上手く表現できなくなる。
ダメな例 ,-- 50→ a11 --100→ a12 -- 80 --, | ↓ s -- 60→ a21 --100→ a22 -- 20 -→ t | ↑ `- 130→ a31 --100→ a32 -- 30 --'
3択を2択にする。簡単のため、1つの廃棄物 $A$ についてだけ考える。
| $A$ | |
|---|---|
| 燃やす | 100 |
| 埋める | 50 |
| 壊す | 80 |
そして、頂点を２分割し、グループ $S,T$ を以下のように意味づける。
ちゃんと各頂点が「$S,T$ のどちらかの状態を必ず取る」ようになっている。
- $A_1$ にとって、$S$ は「燃やす」、$T$ は「燃やす以外の処理をする」
- $A_2$ にとって、$S$ は「埋める以外の処理をする」、$T$ は「埋める」
下図ようにグラフを作る。「○○以外の処理をする」のコストは、便宜上「壊す」コストとする。
「燃やす」と「埋める」を同時に行うのは矛盾なので、$A_1$ が $S$ で $A_2$ が $T$ となることがないよう、$A_1→A_2$ へ無限大の辺を張る。
,-- 80→ A1 -- 100--, s ↓∞ t `-- 50→ A2 --- 80--'
その上で、$A_1$ と $A_2$ の組合せで、以下のように意味づける
- $(S,S)$：「燃やす」と「埋める以外の処理」が選ばれた場合、燃やす
- $(T,T)$：「燃やす以外の処理」と「埋める」が選ばれた場合、埋める
- $(T,S)$：「燃やす以外の処理」と「埋める以外の処理」が選ばれた場合、壊す
どの選択肢も余分に「○○以外の処理」を1つだけカットするので、 あらかじめその分の補償金（＝壊すコスト80円）をもらっておく。
例の場合、$A_1,A_2$ とも $T$ に属させるのが最小となり、埋めるのがよいとわかる（自明だが）。
コストは50+80=130に、あらかじめもらった80を引き、50となる。
廃棄物を2つに増やし、2要素間の制約条件を考える。
| $A$ | $B$ | |
|---|---|---|
| 燃やす | 100 | 200 |
| 埋める | 50 | 240 |
| 壊す | 80 | 500 |
- 制約条件
- $B$ を燃やし、$A$ を埋めると罰金100円
制約条件を加える前のグラフは、このようになる。
,-- 80→ A1 - 100 --, | ↓∞ | |-- 50→ A2 -- 80 --| s t |- 500→ B1 - 200 --| | ↓∞ | `- 240→ B2 - 500 --'
ここで、制約条件を分割後のノードで解釈すると「$B_1$ が $S$ で、$A_2$ が $T$ の場合、罰金が発生する」となる。
それに添うように辺を追加すると、目的のグラフが完成する。
,-- 80→ A1 - 100 --, | ↓∞ | |-- 50→ A2 -- 80 --| s ↑100 t |- 500→ B1 - 200 --| | ↓∞ | `- 240→ B2 - 500 --'
最小カットは
,-- | → [T]A1 - 100 --, | ↓∞ | |-- | → [T]A2 -- 80 --| 80+50+100+200+500 - (80+500) = 350 s ---- t |- 500→ [S]B1 - | --| | ↓∞ | `- 240→ [S]B2 - | --' ,-- | → [T]A1 - 100 --, | ↓∞ | |-- 50→ [S]A2 -- | --| 80+80+200+500 - (80+500) = 280 s ↑100 t |- 500→ [S]B1 - | --| | ↓∞ | `- 240→ [S]B2 - | --'
となり、$A$ は単独なら埋めた方がよいところ、制約条件の追加によって壊すに変化する。
4択以上は（この考え方では）無理
この考え方では、4択以上の選択肢は表現できない。
『「燃やす」と「埋める」を同時に行うと罰金∞』という制約辺をはる必要があるので、 どっちかの意味合いを反転させなければならない。
4択では頂点が3つ必要なので、どれかの組で同じ側に来てしまう。
制約条件に3つの選択肢が入り乱れるのは厳しい
「壊す」を直接表現する頂点がないので、その状態を示す辺は追加できない（上手くする方法はあるのかも? 未調査）
一応、制約条件によっては、廃棄物毎に $S,T$ に割り当てる状態を「燃やす」「埋める」「壊す」から適切に選ぶことで 表現できるかもしれないが、、、
$K$ 択の選択肢
より汎用的に $K$ 択の選択肢を表現することも、条件が限られ、また実装が重くなるが、できる。
-
- 一応、ネタバレ防止のため記事名中の問題名は伏す
- 例題
- $N$ 個の廃棄物を、$K=5$ 通りの処分方法①～⑤から1つ選んで処分する
- 廃棄物 $i=1,2,...,N$ に対し、処分方法 $j=1,...,K$ を選んだ際のコストは $C_{i,j}$
- 廃棄物 $i$ で方法 $x$ をとり、$j$ で方法 $y$ を取ると追加でコスト $D_{i,j,x,y}$
追加コスト $D$ の条件がざっくり下記のいずれかならできる。
- 条件が「以上、以下」の形のみからなる
- 廃棄物 $i$ の処分方法の番号が $x_i$ 以下の時、$j$ の番号が $y_i$ 以上だと正のコスト
- 廃棄物 $i$ の処分方法の番号が $x_i$ 以下の時、$j$ の番号が $y_i$ 以下だと負のコスト
- コスト行列がMonge性を満たす
- 後述
まぁ、競技プログラミングで出るなら都合のいい条件になっていることも多いけど。
頂点の意味合い
ひとまず聞き慣れないMongeとかの制約条件は置いておいて、頂点に対する意味合いを決める。
廃棄物ごとに $K-1=4$ 個の頂点を作り、最小カット問題に落とし込む。
ある廃棄物 $A$ について、各頂点に $S$ が割り当てられたときの意味合いは、次の方法で処分することとする。 （$T$ のときは、それ以外の選択肢を選ぶことを意味する）
- $A_1$：$①$
- $A_2$：$①または②$
- $A_3$：$①または②または③$
- $A_4$：$①または②または③または④$
当然だが、「①または②」であるなら、必ず「①または②または③」である。
言い換えると、$A_2$ が $S$ なら $A_3$ が $T$ であってはいけないので、隣接する頂点間にこのような制約を入れる。
- $A_i→A_{i+1}$ にコスト∞の辺をはる
2つ以上離れた頂点間の制約は考慮しなくていい。（隣接する $i$ に制約を張ってしまえば、$(A_1,A_2,A_3,A_4)$ に割り振られるのは $(T,T,S,S)$ のように、どこかまで全て $T$ でそれ以降全て $S$、という状態になることが保証される）
はじめて $T$ から $S$ になるところを $A_i$ とすると、廃棄物 $A$ が取るべき選択肢は $i$ ということになる。
もし全て $T$ なら、⑤である。
燃やす埋めるフォーマットのグラフにすると、以下のようになる。
処分方法 ① ② ③ ④ ⑤ コストa 60 10 150 30 100 ,----- 0 ---- A1 --(a1-a2= 50)--, | ↓∞ | |----- 0 ---- A2 --(a2-a3=-140)--| s ↓∞ t |----- 0 ---- A3 --(a3-a4= 120)--| | ↓∞ | `--(a5=100)-- A4 --(a4 = 30)--'
辺のコストを差分にすることで、
$A_1～A_4$ に SSSS を割り当てると $a_1$、TSSS を割り当てると $a_2$ など、
$A_1～A_4$ の頂点に持たせた意味とコストが一致するようになる。
負のコストが発生しうるので、元の燃やす埋める問題と同様の対処方法で、適宜、あらかじめもらったことにするなどで調整する。
また、必ずしも $s-(縦に並んだ頂点)-t$ という形にこだわらなければ、以下のようにも表現される。
s --(a5=100)--> A4 --(a4=30)--> A3 --(a3=150)--> A2 --(a2=10)--> A1 --(a1=60)--> t
^---- ∞ -----' ^---- ∞ ----' ^---- ∞ ----'
これも、最小カットを考えると $S$ と $T$ の境界のみコストがかかるので、正しく動作する。
ここから更に辺を追加していくことを考えると、紙などに書いて考えるのはこっちの方がやりやすいかも。
なお、負のコスト（賞金）が発生する場合は、最小値を $-x$ として、「全ての辺に $x$ ずつ加算しておき、最終結果から $x$ を引く」とよい。
2要素間の追加コスト
頂点に前述のような意味合いを持たせたので、追加コストの条件は「以上、以下」の関係に対して張ることができる。
- 表現可能な2要素間の追加コスト
- $A$ の処分方法の番号が $x_i$ 以下の時に、$B$ の番号が $y_i$ より大きいと、コスト $c_i$
- $B$ の処分方法の番号が $x_i$ 以下の時に、$B$ の番号が $y_i$ 以下だと、賞金 $c_i$
たとえば $x_i=3$、$y_i=2$ だとすると、（$B_1～B_4$ の意味合いも $A_1～A_4$ と同様に定義するとして）
- 「$A$ の番号が 3 以下」は「頂点 $A_3$ が $S$」
- 「$B$ の番号が 2 より大きい」は「頂点 $B_2$ が $T$」
であることを示すので、$A_3→B_2$ に容量 $c_i$ の辺を張ればよいと分かる。
v-- ∞ ---, v-- ∞ ---, v-- ∞ ---,
,--(a5)--> A4 --(a4)--> A3 --(a3)--> A2 --(a2)--> A1 --(a1)--,
| | |
s `---(ci)----, t
| v |
`--(b5)--> B4 --(b4)--> B3 --(b3)--> B2 --(b2)--> B1 --(b1)--'
^-- ∞ ---' ^-- ∞ ---' ^-- ∞ ---'
では、同じ $A,B$ に、条件 $x_i,y_i,c_i$ が複数個ある場合は？
ここで必要となってくるのが、コストのMonge性となる。
“以上、以下”の話はいったん忘れて、やっぱり $A,B$ それぞれが特定の処分方法の場合にかかるコストが行列で定義されているとする。これを $A,B$ 間のコスト行列とする。
A\B ① ② ③ ④ ⑤ ① 1 2 4 7 11 ② 2 3 5 8 12 ③ 4 5 6 9 13 ④ 7 8 9 10 14 ⑤ 11 12 13 14 16
この時、行列の任意の長方形の角4点の値に対し、「／の和 ≧ ＼の和」が成立する性質を、Monge性という。
A\B ① ② ③ ④ ⑤ ① 1 2 4 7 11 5+7 >= 2+9 ② [2] 3 [5] 8 12 ③ 4 5 6 9 13 ※この行列では、他の部分でもこの性質は全て成り立つ ④ [7] 8 [9]10 14 ⑤ 11 12 13 14 16
で、このコスト行列（廃棄物が3個以上ある場合は、全てのコスト行列）がMonge性を持てば、 最小カットで解けるようなグラフを構築できるとされている。
先ほどの「Aが③以下でBが②より大きいならコスト $c$」というのも、行列にすると
A\B ① ② ③ ④ ⑤ ① 0 0 c c c ② 0 0 c c c ③ 0 0 c c c ④ 0 0 0 0 0 ⑤ 0 0 0 0 0
こういう形になるので、Monge性を持っている。右上から伸びる長方形のような形となる。
辺の張り方
まず、Monge性は、1つの行や列に定数を加算しても保たれるという性質がある。
- 必ずコスト $X$ はかかるものとして、コスト行列全体から $X$ を引き、最終コストに加える
- $A$ で②を選ぶと余分に $Y$ のコストがかかることにして、コスト行列の2行目から $Y$ を引く
などの処理をすることで、コスト行列の「最終行と1列目」を0に揃えることができる。
A\B ① ② ③ ④ ⑤ A\B ① ② ③ ④ ⑤ ① 1 2 4 7 11 ① 0 0 1 3 5 ② 2 3 5 8 12 ② 0 0 1 3 5 ③ 4 5 6 9 13 → ③ 0 0 0 2 4 ④ 7 8 9 10 14 ④ 0 0 0 0 2 ⑤ 11 12 13 14 16 ⑤ 0 0 0 0 0
そうすると残るのは、右上に向かって大きくなっていく行列である。
Monge性から、これは複数の右上から伸びる長方形の和で表現できる。
つまり「$A$ が③以下で $B$ が③より大きいとコスト 1」などの条件の和で表現できる。
0 0 1 3 5 0 0 1 1 1 0 0 0 2 2 0 0 0 0 2 0 0 1 3 5 0 0 1 1 1 0 0 0 2 2 0 0 0 0 2 0 0 0 2 4 = 0 0 0 0 0 + 0 0 0 2 2 + 0 0 0 0 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
具体的には、ある2×2の部分（左上を $(i,j)$ とする。$1 \le i,j \le 4$）に着目して、
・● ●・ ●・ の和 － ・● の和 ＞ 0
なら、$A_i→B_j$ にその差分だけの辺を張ればよい。
なんか $A→B$ の辺だけできちゃうけど大丈夫？
$B→A$ の辺（に相当するコスト）は、コスト行列に一定値を足し引きする過程で既に考慮されてるので大丈夫。
コスト行列の並び替え
「そのままではMonge性が成り立たなくても、適当に行と列を入れ替えれば成り立つ」場合、 入れ替えることでグラフ構築可能である。
この時、2つの廃棄物 $A,B$ で、順番が違っていてもよい。（そもそも、廃棄物毎に選択肢が全く別物であってもよい）
ただし、1つの廃棄物の中での順番は一貫させる必要がある。
つまり廃棄物が3つ以上あって、$A,B$ のコスト行列でMonge性を成り立たせるために $A$ を並べ替えた場合、
$A,C$ など他とのコスト行列においても、$A$ は並べ替えた順番で固定する必要がある。
INFコストに注意
コスト無限大を表現するのに、実装上、巨大な定数で無限を表現する場合、 コスト行列におけるMonge性の判定が狂うことがある。
0 [∞ ∞] [ ]の部分において、無限大を定数とすると 0 [ 0 ∞] Monge性や、行や列に定数を足し引きしての 0 0 0 コスト行列の変換が成り立たない。 0 ∞ ∞ 0 ∞ ∞ 無理矢理左と下を0にそろえても、 ∞ 0 ∞ → 0 -∞ ∞ 負の値が出てきてしまう ∞ ∞ 0 0 0 0
（数学的にこういう表現はしないけど）本来、重なり合ってるはずなんだよね。これなら成り立つ。
0 ∞ 2∞ 0 0 ∞ 0 0 0
解決する手段はあるらしいが、未調査。
参考
Project Selection Problemという、似た考え方の解法もある。
劣モジュラ関数という概念を使って、どんな問題なら可能かを説明されている。
