模拟费用流 总结
学习自https://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 Brightarrow 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)的情况，这样就不优了。
