模拟费用流总结

模拟费用流 总结

学习自https://www.luogu.com.cn/blog/command-block/mu-ni-fei-yong-liu-xiao-ji

可以系统地解决一系列贪心问题的思想。

操作步骤

• 首先对于一个问题建立费用流模型，注意这时候可以得到问题的凸性(convexity)，可以用一些其它方法对问题进行简化（如wqs二分），然后观察费用流模型的特殊性，考虑快速算费用流。

• 一般而言，可以考虑图的增量对答案的贡献，或者按照EK算法以某种顺序求增广路，注意反向边的贡献（比如负环）。一般用堆来维护，也有时候可以直接维护出一些东西然后做。

• 将费用流模型和原问题结合起来考虑，往往会比较容易得到一些性质。

---

例题

CF865D Buy Low Sell High（老鼠进洞·壹）

题意：已知接下来n" role="presentation">n$n$天的股票价格，每天你可以买进一股股票，卖出一股股票，或者什么也不做。假设你拥有无限本金，求n" role="presentation">n$n$天之后能得到的最大利润。

容易得到费用流模型：相邻点双向(+∞,0)" role="presentation">(+∞,0)$(+\mathrm{\infty },0)$，源点向每个点(1,ci)" role="presentation">(1,ci)$(1,c_i)$，每个点向终点(1,−ci)" role="presentation">(1,−ci)$(1,-c_i)$求最小费用可行流。

考虑增量贡献，第一种情况是选择某天买进今天卖出，第二种情况是选择之前卖出的某天换到今天卖出，对应到费用流上就是一条普通的增广路和负环，那么维护一个堆就做完了。

---

洛谷 P1484 种树

题意：一条直线上n" role="presentation">n$n$个坑，可以在坑里面种一棵树，不能在相邻两个坑内种树，每个坑内种树有价值ai" role="presentation">ai$a_i$，求k个点最大价值。

费用流建模就考虑相邻不能同时选的限制，把间隔变成点，分奇数间隔和偶数间隔中间连边，边就是坑，然后中间边就是(1,ai)" role="presentation">(1,ai)$(1,a_i)$，其它边都是(1,0)" role="presentation">(1,0)$(1,0)$，流量限制为k" role="presentation">k$k$

这样就证明了原问题是关于k" role="presentation">k$k$的凸函数，可以wqs二分+dp求解，比较经典。

当然这里讲的是模拟费用流。

考虑模拟EK算法，找增广路。

显然除了源点和汇点连的边，只会经过中间的边，也就是一段连续区间状态取反。

这样的话对应回原问题，两边的两个坑一定是空。那么给我们一个思路：维护两边都是空的区间，每次增广相当于合并三个区间，用双向链表+堆维护即可。

---

[[Lydsy1708月赛]跳伞求生（老鼠进洞·贰）

题意：老鼠进洞·壹之中选洞有额外贡献。

费用流建图类似。依旧考虑增量，两种情况：

• 源点连出来的边之前的源点连出来的边形成负环
• 多一条增广路

随便用堆维护一下就好了。

---

[NEERC2016]Mole Tunnels（老鼠进树洞）

题意：老鼠上树进洞，对所有k" role="presentation">k$k$求前k" role="presentation">k$k$只老鼠全部进洞最小代价。

建图就是源点向老鼠点连(1,−∞)" role="presentation">(1,−∞)$(1,-\mathrm{\infty })$，这样所有老鼠必选。

按照询问顺序考虑增量。因为必须满流所以不存在负环，那么只需考虑新的增广路，那么就很简单了，在完全二叉树上维护到当前子树最近的点和距离，然后每次加一只老鼠就跳父亲去找，然后跳父亲更新，由于完全二叉树的优良性质复杂度就是O(nlog⁡n)" role="presentation">O(nlogn)$O(n\log n)$的了。

---

[NOI2019] 序列

题意：n" role="presentation">n$n$对数(ai,bi)" role="presentation">(ai,bi)$(a_i,b_i)$，[1,n]" role="presentation">[1,n]$[1,n]$中选两个大小为k" role="presentation">k$k$的集合A,B" role="presentation">A,B$A,B$，使得|A∩B|=L" role="presentation">|A∩B|=L$|A\cap B|=L$求max{∑i∈Aai+∑i∈Bbi}" role="presentation">max{∑i∈Aai+∑i∈Bbi}$max\{\sum _{i\in A}{a}_i+\sum _{i\in B}{b}_i\}$。

建图需要稍微思考一下，很难满足|A∩B|=L" role="presentation">|A∩B|=L$|A\cap B|=L$的条件，那么不妨反过来，满足A" role="presentation">A$A$和B" role="presentation">B$B$不同的对数至多为k−L" role="presentation">k−L$k-L$。

连边(S,Ai,1,ai),(Ai,Bi,1,0),(Bi,T,1,bi),(Ai,P,1,0),(P,Q,k−L,0),(Q,Bi,1,0)" role="presentation">(S,Ai,1,ai),(Ai,Bi,1,0),(Bi,T,1,bi),(Ai,P,1,0),(P,Q,k−L,0),(Q,Bi,1,0)$(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算法，有下列合法情况：

1. S→A→B→T" role="presentation">S→A→B→T$S\to A\to B\to T$
2. S→A→P→A′→B′→T" role="presentation">S→A→P→A′→B′→T$S\to A\to P\to A^{\prime }\to B^{\prime }\to T$
3. S→A→B→Q→B′→T" role="presentation">S→A→B→Q→B′→T$S\to A\to B\to Q\to B^{\prime }\to T$
4. S→A→B→Q→P→A′→B′→T" role="presentation">S→A→B→Q→P→A′→B′→T$S\to A\to B\to Q\to P\to A^{\prime }\to B^{\prime }\to T$
5. S→A→P→Q→B→T" role="presentation">S→A→P→Q→B→T$S\to A\to P\to Q\to B\to T$

事实上还有一类情况形如S→A→B→Q→B′→A′→P→A″→B″......" role="presentation">S→A→B→Q→B′→A′→P→A′′→B′′......$S\to A\to B\to Q\to B^{\prime }\to A^{\prime }\to P\to A^{″}\to B^{″}......$

然而可以发现出现这样情况的前提已经是不优的了，所以可以不用考虑。

剩下就是考虑这5" role="presentation">5$5$种情况的实际贡献，就是连着S" role="presentation">S$S$和T" role="presentation">T$T$的两个点。

于是维护5" role="presentation">5$5$个堆即可。

细节：增广优先顺序是1→4→2→3→5" role="presentation">1→4→2→3→5$1\to 4\to 2\to 3\to 5$，否则会出现其它边没有流满L" role="presentation">L$L$且下标相等的数对用了P→Q" role="presentation">P→Q$P\to Q$的情况，这样就不优了。