模拟费用流小记

· · 算法·理论

唉，挑战以前学的非常垃圾的板块，现在学起来其实并没有想象中的困难，还是以前太摆了。

费用流的性质

EK : 每次寻找最短的增广路进行增广。

可以直接模拟上述算法的思路，也可以基于这些算法的正确性，设计类似的规则。

最小费用任意流: 可用 EK 求解，每次增广最短路，当单次费用为正时停止。

负费用最大流：可用 EK 求解，每次增广最短路，当总费用非正时停止。

增量-最小费用任意流: 每次在图中增加一些点和边，并求解新的最小费用任意流。

只需考虑所有新的 “源到汇的负路径” 以及 “负环” 的贡献。

也可以看做源和汇之间有容量为无穷的边连接，这样“源到汇的负路径”实际上就是“负环”。

一些比较重要的结论：

CF2029I Variance Challenge

https://www.luogu.com.cn/article/1o8rs7ly

[省选联考 2023] 人员调度

唉，其实就是增量-最大费用任意流的板子。

费用流的模型非常容易建出。

只需考虑新加入的一个点形成的增广路以及与 s 形成的正环（相当于就是退流）。

先看增广路，这个好弄，先求出通过反向边能爬到的最高处（这个树剖+二分），然后用 segment-tree 维护一下空位置即可。注意同时要修改反向边的流量。

再看正环，也很傻逼，同样求出通过反向边能爬到的最高处，画画发现就是与现在有匹配的点形成正环，对于树上的每个点维护一个 set 即可，然后把每个 set 的最小值丢进 segment-tree 即可，做完了。

剩下套一个线段树分治即可。太几把难写了，特别是狗屎撤销那里，要吐了。复杂度 3log。

P6122 [NEERC2016]Mole Tunnels

非常经典的老鼠进洞问题啊。

这里只要是想讲清楚为什么在知道 S 一定满流的情况下与其相关的边不会退流。首先先把模型建出来，由于要求满流，考虑与 S 相连的边的费用全部减去一个极大值 C，最后加回来即可。那么转化为增量-最小费用任意流。考虑加入一个老鼠，此时会产生新的增广路以及与 S 相关的负环，但是注意到与 S 相关的负环一定是不优秀的，因为其权值为 -C+C+d_1，而增广路的权值为 d_2-C，而 C 是一个极大值，那么肯定选增广路最优秀。于是只需要暴力维护增广路即可，这是个二叉树，随便想怎么维护就怎么维护。

CF865D Buy Low Sell High

非常简单的题目，分析一下增广路和产生的负环的贡献即可。

CF730I - Olympiad in Programming and Sports

我测，我怎么一上来就在想动态加点，简直弱智死了。

其实直接建静态图然后模拟其 4 种增广路即可，大概就是选 team 1 ，选 team 2，选一个 team1 并把一个 team1 的人踢到 team2，选一个 team2 并把一个 team2 的人踢到 team1。开 4 个堆暴力模拟即可。

教训：别动不动就增量-模拟费用流，退流会增加负环的讨论。

【UER #8】雪灾与外卖

恶心吐了，看了一晚上都没懂这个勾八题。

感觉非常逆天，很抽象的反悔贪心。最让人迷惑的一个点是似乎存在一个结论为当一个店反悔时，自动认为这个人反悔成上一次匹配的店。也就是认为店和人不会同时反悔，还有倒流的机会。不过也不是完全不能理解，首先有两个结论分别是：1.无交叉匹配 2.包含匹配时这些匹配的方向相同，否则调整后更优秀。然后可以自己手画一下似乎两个都反悔时违背这个结论。算了，不懂，反正我看当时没人做出来，这下我要狠狠的点踩这个狗屎题了。

「LibreOJ NOI Round #2」黄金矿工/「ICPC World Finals 2018」征服世界

两个狗屎题目。

这个黄金矿工只能说是跟那个省选题一个妈妈生的，首先路径的代价可以省去，把黄金和矿工的权值改成与深度有关的就行。这个题比省选题困难的地方在于新增黄金，然后会产生与 t 相关的负环。如果暴力搜索能够通过反向边到达的黄金，那么肯定 tle。考虑重链剖分，每个点只维护其轻子树中的黄金能够通过反向边到达该点的黄金中代价最小那一个。那么查询就很 easy 了，不断地往上跳重链，并把当前所在的重链拉出来，然后往下看最低能到达重链的什么地方，直接查询即可，算了，说不太清楚，画个图就很明显了。维护这个轻子树中的答案是 easy 的，同样的往上跳重链即可。

「ICPC World Finals 2018」征服世界。这个更加狗屎，存在 \mathcal{O}(n\log^2n) 的做法。首先自身每个点先自匹配，也就是令 a_i=x_i-y_i，a_i<0 的就看成需要跟其他坑匹配的，a_i>0 就看成坑。考虑把需要匹配的依次加入，由于需要强制其满流，所以与 S 相连的边不会退流！只需要考虑新增的增广路即可，这个初看超级难维护，因为这是双向边，而且还可能存在负权值的反向边，所以直接来就爆炸了。考虑换根，实时维护每个点到当前 dfs 到的点的最小距离，然后选择增广路后要更新边的流量，每次直接暴力判断经过每条边的权值现在应该是正还是负，如果有需要翻转的就直接拉出来翻转。考虑证明该做法的复杂度正确性，在 dfs 这个点外面的时候，增广路只会进来，dfs 到这个点的子树中时，增广路只会出去，dfs 最后出去的时候，增广路只会进来，所以每条边的流量只会经过常数次从非 0 到 0 的变化（也就是需要翻转的次数）。代码用脑子想想就是一坨，狗都不写。

感觉有点明白 雪灾与外卖 和 「ICPC World Finals 2018」征服世界 这两个题的简单反悔贪心做法了。首先使用这个做法需要满足反悔的两个对象中只会有一个反悔，两个反悔时可以证明一定不优，其中 ICPC World Finals 2018」征服世界 这题是很好看出来的，因为两个都反悔会导致路径重合。当一个东西想要反悔时，需要让当前匹配的另一个东西回到之前的状态（而堆里存储的就是这个回到过去的代价），那么新的匹配的代价就是两个原先对应的匹配回到过去的代价加上新匹配的代价。

[PA2013] Raper

先 wqs 二分转化为增量-最小费用任意流，然后反悔贪心直接做就行了。不知道为啥 pbds 的堆这么慢，注意二分时爆 int 的问题，不然会莫名其妙 tle。

https://oi-wiki.org/lang/pb-ds/pq/

建议一般还是用普通堆。