Project Selection 問題的 cheatsheet

$S, T$ 分別代表 $0, 1$ 側，最小化總費用。

如何還原解：在 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