Project Selection Cheatsheet
Project Selection 問題的 cheatsheet
$S, T$ 分別代表 $0, 1$ 側，最小化總費用。
| 費用函數 ($c \geq 0$) | 加邊 | 說明 |
|---|---|---|
| $i$ 為 $0$ 時費用增加 $c$ | $(i, T, c)$ | $T$ 必定在 $1$ 側，所以「$i$ 在 $0$ 側」與「這條邊要被割」同值 |
| $i$ 為 $1$ 時費用增加 $c$ | $(S, i, c)$ | |
| $i$ 為 $0$ 時費用減少 $c$ | 直接得到 $c$；$(S, i, c)$ | 反過來用扣的算 |
| $i$ 為 $1$ 時費用減少 $c$ | 直接得到 $c$；$(i, T, c)$ | |
| $i$ 為 $0$，$j$ 為 $1$ 時費用增加 $c$ | $(i, j, c)$ | 邊是有向的 |
| $i, j$ 不相等時，費用增加 $c$ | $(i, j, c), (j, i, c)$ | |
| $i, j$ 有任何一個為 $1$ 時，費用增加 $c$ | $(S, i, c), (i, j, c)$ | 此處可以不需要新增輔助節點，建出來的 model 頂點數比較少 |
| $i, j$ 有任何一個為 $0$ 時，費用增加 $c$ | $(i, j, c), (j, T, c)$ | |
| $i, j$ 同時是 $0$ 時，費用減少 $c$ | 直接得到 $c$；$(S, i, c), (i, j, c)$ | 反過來用扣的算 |
| $i, j$ 同時是 $1$ 時，費用減少 $c$ | 直接得到 $c$；$(i, j, c), (j, T, c)$ | |
| $i \in I$ 有任何一個為 $0$ 時，費用增加 $c$ | 新增輔助節點 $w$；$(i, w, \infty), (w, T, c)$ | |
| $i \in I$ 有任何一個為 $1$ 時，費用增加 $c$ | 新增輔助節點 $w$；$(S, w, c), (w, i, \infty)$ |
如何還原解：在 residual network 上 BFS 得到最小割（從 $S$ 走得到的就屬於 $S$ 那邊，否則就屬於 $T$ 那邊）
說明
日文為「燃やす埋める」，英文為 Project Selection 的問題，眾所周知（？）可以化約成最小割問題，最小割問題則通常是用最大流解決。
通常來說，Project Selection 的題目就是會有 $N$ 個物件，每個物件你要決定選或不選（在日文的語境是垃圾要用燒的或者用埋的XD），並且會有一個費用函數是根據你選了哪些物件決定費用，希望決定每個物件選或不選來最小化費用。若費用函數可以寫成數個函數 $f_1, f_2, \dots$ 的和，且每個 $f_i$ 都可以從上表查到的話，那直接按表建邊跑最大流就可以得到答案了。
之前校內賽驗題的時候發現 ckiseki 的 codebook 的 cheatsheet 在「$i, j$ 有任何一個為 $1$ 時，費用增加 $c$」需要新增一個輔助節點，在該題就會直接從 $N$ 個節點變成 $N^2$ 個節點。雖然說最後算出來兩個模型上面跑 Dinic 估計的時間複雜度其實是一樣的，但拿來當 library 的東西總是會希望連常數都比較小，於是就順便來水一篇文。
注意到上表中並不是兩個變數的所有情形都有列出來，畢竟我們不可能簡簡單單就用 flow 解決 max-2-sat 這個 NP-complete 問題。如果查表發現查不出來的話，除了可能可以 tweak 一下費用函數（例如調整不同變數 $0, 1$ 側代表的意義）以外，也有可能其實預期解不是 flow。若發現自己最後化約成了一個 max-cut 的問題的話（注意上表 $c$ 都 $\geq 0$，因為邊容量需要非負），那壞消息是 max-cut 是 NP-hard，可能要換點方法。
reference
https://qiita.com/ningenMe/items/69ed7ce43c9cd0a2de38
https://ei1333.github.io/luzhiled/snippets/memo/project-selection.html
https://theory-and-me.hatenablog.com/entry/2020/03/13/180935