網路流練習筆記
一些常用的套路：
- 必須完成的一些目標，可以考慮搞進流量中，因為跑最大流的話肯定會流滿，也就相當於強制地完成了那些目標。
- 拆點。然後可以通過兩點之間連某個容量的邊來限制該點取到的次數。
- 建立超級源點、匯點。幾乎在每道題中都會用到，不光方便計算，還可以通過連邊的方式對某些狀態進行操作。
P1251 餐巾計劃問題
發現每天開始和結束時的狀態是不一樣的，考慮拆點。
接著怎麼辦？模擬餐巾的路線嗎？
假如從白天向晚上連一條邊表示餐巾由乾淨變為髒的話，會發現根本無法處理每天的需求量。
那反正只要是乾淨的就行了，咋來的咱不管，那就直接從超級源點流過來嘛。然後就可以讓餐巾流到超級匯點來完成需求啦！
具體分以下幾種：
- 由超級源點向每天晚上連一條容量為當日需求，費用為 \(0\) 的邊。表示晚上獲得臟餐巾。
- 由每天早上向超級匯點連一條容量為當日需求，費用為 \(0\) 的邊。表示白天需要新餐巾。
- 由每天晚上向次日晚上連一條容量為 \(\infty\)，費用為 \(0\) 的邊。表示餐巾不洗留到下一天。
- 由每天晚上向現在送去快洗能洗好的那天早上連一條容量為 \(\infty\)，費用為快洗費用的邊。表示送去快洗。
- 由每天晚上向現在送去慢洗能洗好的那天早上連一條容量為 \(\infty\)，費用為慢洗費用的邊。表示送去慢洗。
- 由超級源點向每天早上連一條容量為 \(\infty\)，費用為購買新餐巾費用的邊。表示購買新餐巾。
值得注意的是，第三點處於貪心的考慮，肯定會直接洗掉。但我們發現設計的方案中並沒有設置這樣一個庫存餐巾，所以就得通過這一步來使得餐巾能夠在必須洗的那天晚上剛好洗掉，從而達到和提前洗完一樣的效果。所以如果某天晚上就算送去快洗也洗不完了，前一天晚上的這條邊可以不連。
