首页 cms教程 正文
模拟费用流总结

 2022-10-15    bigbai  

模拟费用流 总结

学习自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算法,有下列合法情况:

  1. \(S \rightarrow A \rightarrow B\rightarrow T\)
  2. \(S \rightarrow A \rightarrow P \rightarrow A' \rightarrow B' \rightarrow T\)
  3. \(S \rightarrow A \rightarrow B \rightarrow Q \rightarrow B' \rightarrow T\)
  4. \(S \rightarrow A \rightarrow B \rightarrow Q \rightarrow P \rightarrow A' \rightarrow B' \rightarrow T\)
  5. \(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\)的情况,这样就不优了。

  •  标签:  

原文链接:https://www.bigbai.cc/news/1414.html

本文版权:如无特别标注,本站文章均为原创。