一些反悔贪心与模拟费用流

前言

模拟费用流的主要思想是把问题建成费用流问题后不去直接用费用流算法去跑，而是考虑用某些其他更高效的方法来计算费用流，不过后者的难点在于计算的算法要因图而异，不过对像我这样比较笨的人来讲设计费用流比设计反悔贪心容易多了，其中一部分原因是费用流结果的最大/最小性是由流理论的万全性保证的，我不需要像反悔贪心一样花费时间去验证反悔机制设计的是完全的，故写此文以记之。

例题一 P2949 [USACO09OPEN] Work Scheduling G

最trivial的形式, 考虑建起这样的图

• 拉一条时间轴，时间 i+1 向 时间 i 连 (inf,0) 的边
• 对于工作 i，从源点向 时间 D_i 连一条 (1,P[i]) 的边
• 每个时间 i 向汇点连一条 (1,0) 的边

于是答案就是这个网络的最大费用最大流，这里采取的模拟思路是初始的时候只有 时间 0、源点和汇点，我们从小到大地加入 时间 i 节点并且练接上这个节点与已经加入的节点的边，之后考虑维护最大费用。

假定我们已经加入了 时间 0 到 时间 i 的节点，那么如果加入 时间 i+1 能够使得答案更大，那么一定存在经过 时间 i+1 的流量。于是我们考察在当前的图里有哪些流量可能流经 时间 i+1 ，其一是那个从 时间 i+1 流向汇点的流量(注意 时间 i+2 还未被加入图中)，其二是从 时间 i+1 流向 时间 i 的流量。前一种流量的情形是平凡的，我们考虑后一种流量在进入 时间 i 后去向如何：如果到此时此刻 时间 0 到 时间 i 之间仍然存在空余的流向源点的流量，每次就可以挑选当前流入 时间 i+1 的最大费用的流量直接流过去，当然这种情况就是增广路的情形；那当我们找不到增广路的时候就要考虑环流的情形，这里我们能够很轻松地去讨论环流的原因就是因为图很简单，每个经过 时间 i+1 的环流一定是形如

于是权值最大的环流就是最大的流入 时间 i+1 的边减去最小的以前流入到某个 时间 j 的边，所以我们需要维护流入的边的最小值。而我们不需要去考虑复杂环或/增广路，因为如果最大环/增广路是复杂环/增广路那么就意味着存在不经过 时间 i 的正环流，与答案的最大性矛盾了。

在这一通分析后我们要维护的东西已经确定了：

• 维护截至目前有多少个空余的时间节点
• 维护已经流入时间节点的流有哪些，并将它们从小到大排列起来
• 维护目前的最大费用

第二点用堆或者set来维护即可，那么这个题就完成了。

例题二 CF865D Buy Low Sell High

这个题目的解法和例题一是一样的，都是考虑加入点。我们先来建图

• 建立一条时间轴，时间 i 向 时间 i+1 连接一条 (inf,0) 的边
• 对于第 i 天，源点向 时间 i 连接一条 (1,-p_i) 的边，时间 i 向汇点连接一条 (1,p_i) 的边

答案就是这个网络的最大费用，初始的时候只有源汇点与 时间 0 ，考虑每次加入 时间 i+1 会导致什么。情形可能更简单一点，所有有意义的流量都是从 时间 i 流入的，其中简单增广路是形如

所以我们需要找到先前的最大的没有流入时间节点的边；而简单环是形如

所以我们需要找到先前的最小的从时间节点到汇点的边。于是我们为这两个量分别维护一个堆就可以了。

例题三 P1792 [国家集训队] 种树

这一次我们不能采用拓展点的方法了，因为这个图比较复杂，环流并不能很简单的维护。于是我们采取的方法是一开始就把图建好之后每次都找增广路，不过我们使用数据结构来优化增广的过程。首先我们建图

• 建立 n+1 个位置节点：坑 0 到 坑 n
• 偶数坑向汇点连接 (1,0) 的边，源点向奇数坑连接 (1,0) 的边
• 偶数坑向相邻的两个奇数点连边，容量为 1 ，费用从左到右填每个坑的价值

我们选择不断增广的另外一个原因是这个题目是不会有非简单增广路出现的（即不存在负环），当然了，大多数网络流的题目都不会出现负环，不然我们还需要提前做消圈处理。

于是我们可以维护目前存在的所有增广方案，注意每次我们只增广一单位流量，所以增广的方案实际上是 O(n) 级别的，之后我们讨论每次增广后对增广方案的影响是怎么样的，这个影响的范围是 O(1) 的，所以我们就可以直接暴力地把这个影响添加到方案里，所以我们可能就需要 set 而不是堆了。

例题四 P5470 [NOI2019] 序列

方向和例题三一样，也是模拟增广。不过这个题目的图就比较复杂了（但是仍然比一般的网络流题目简单），这个情况下我们需要把增广方案分成 O(1) 类，每个类分别去维护一个 set ，然后当我们真的采取某个策略去增广的时候我们需要考虑对其他策略的影响。

总结

后面已经有一些意识流了，可能是我太累了，当然更大的可能是因为这啥比 markdown 不支持画图，网络流的题怎么能不画图呢。但是总而言之用模拟费用流的想法来做反悔贪心的时候我们只需要关注每次增广的时候如何快速取到最大值以及采取某个措施之后怎么快速更新对于其他策略的影响，正确性的问题可以大胆放心地交给流理论来解决。