模擬費用流總結
模擬費用流 總結
學習自//www.luogu.com.cn/blog/command-block/mu-ni-fei-yong-liu-xiao-ji
可以系統地解決一系列貪心問題的思想。
操作步驟
-
首先對於一個問題建立費用流模型，注意這時候可以得到問題的凸性(convexity)，可以用一些其它方法對問題進行簡化（如wqs二分），然後觀察費用流模型的特殊性，考慮快速算費用流。
-
一般而言，可以考慮圖的增量對答案的貢獻，或者按照EK演算法以某種順序求增廣路，注意反向邊的貢獻（比如負環）。一般用堆來維護，也有時候可以直接維護出一些東西然後做。
-
將費用流模型和原問題結合起來考慮，往往會比較容易得到一些性質。
例題
CF865D Buy Low Sell High（老鼠進洞·壹）
題意：已知接下來\(n\)天的股票價格，每天你可以買進一股股票，賣出一股股票，或者什麼也不做。假設你擁有無限本金，求\(n\)天之後能得到的最大利潤。
容易得到費用流模型：相鄰點雙向\((+\infty,0)\)，源點向每個點\((1,c_i)\)，每個點向終點\((1,-c_i)\)求最小費用可行流。
考慮增量貢獻，第一種情況是選擇某天買進今天賣出，第二種情況是選擇之前賣出的某天換到今天賣出，對應到費用流上就是一條普通的增廣路和負環，那麼維護一個堆就做完了。
洛谷 P1484 種樹
題意：一條直線上\(n\)個坑，可以在坑裡面種一棵樹，不能在相鄰兩個坑內種樹，每個坑內種樹有價值\(a_i\)，求k個點最大價值。
費用流建模就考慮相鄰不能同時選的限制，把間隔變成點，分奇數間隔和偶數間隔中間連邊，邊就是坑，然後中間邊就是\((1,a_i)\)，其它邊都是\((1,0)\)，流量限制為\(k\)
這樣就證明了原問題是關於\(k\)的凸函數，可以wqs二分+dp求解，比較經典。
當然這裡講的是模擬費用流。
考慮模擬EK演算法，找增廣路。
顯然除了源點和匯點連的邊，只會經過中間的邊，也就是一段連續區間狀態取反。
這樣的話對應回原問題，兩邊的兩個坑一定是空。那麼給我們一個思路：維護兩邊都是空的區間，每次增廣相當於合併三個區間，用雙向鏈表+堆維護即可。
[[Lydsy1708月賽]跳傘求生（老鼠進洞·貳）
題意：老鼠進洞·壹之中選洞有額外貢獻。
費用流建圖類似。依舊考慮增量，兩種情況：
- 源點連出來的邊之前的源點連出來的邊形成負環
- 多一條增廣路
隨便用堆維護一下就好了。
[NEERC2016]Mole Tunnels（老鼠進樹洞）
題意：老鼠上樹進洞，對所有\(k\)求前\(k\)只老鼠全部進洞最小代價。
建圖就是源點向老鼠點連\((1,-\infty)\)，這樣所有老鼠必選。
按照詢問順序考慮增量。因為必須滿流所以不存在負環，那麼只需考慮新的增廣路，那麼就很簡單了，在完全二叉樹上維護到當前子樹最近的點和距離，然後每次加一隻老鼠就跳父親去找，然後跳父親更新，由於完全二叉樹的優良性質複雜度就是\(O(n \log n)\)的了。
[NOI2019] 序列
題意：\(n\)對數\((a_i,b_i)\)，\([1,n]\)中選兩個大小為\(k\)的集合\(A,B\)，使得\(|A \cap B| = L\)求\(\max\{\sum_{i \in A} a_i + \sum_{i \in B} b_i\}\)。
建圖需要稍微思考一下，很難滿足\(|A \cap B| = L\)的條件，那麼不妨反過來，滿足\(A\)和\(B\)不同的對數至多為\(k-L\)。
連邊\((S, A_i, 1, a_i), (A_i, B_i, 1, 0), (B_i, T, 1, b_i), (A_i, P, 1, 0), (P, Q, k – L, 0), (Q, B_i, 1, 0)\)。
考慮模擬EK演算法，有下列合法情況：
- \(S \rightarrow A \rightarrow B\rightarrow T\)
- \(S \rightarrow A \rightarrow P \rightarrow A’ \rightarrow B’ \rightarrow T\)
- \(S \rightarrow A \rightarrow B \rightarrow Q \rightarrow B’ \rightarrow T\)
- \(S \rightarrow A \rightarrow B \rightarrow Q \rightarrow P \rightarrow A’ \rightarrow B’ \rightarrow T\)
- \(S \rightarrow A \rightarrow P \rightarrow Q \rightarrow B \rightarrow T\)
事實上還有一類情況形如\(S \rightarrow A \rightarrow B \rightarrow Q \rightarrow B’ \rightarrow A’ \rightarrow P \rightarrow A” \rightarrow B” ……\)
然而可以發現出現這樣情況的前提已經是不優的了，所以可以不用考慮。
剩下就是考慮這\(5\)種情況的實際貢獻，就是連著\(S\)和\(T\)的兩個點。
於是維護\(5\)個堆即可。
細節：增廣優先順序是\(1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 5\)，否則會出現其它邊沒有流滿\(L\)且下標相等的數對用了\(P \rightarrow Q\)的情況，這樣就不優了。
