模拟费用流

简介

费用流是解决一些最优化问题的常用算法。可以认为，费用流问题是线性规划问题的一个子集，而模拟费用流又是费用流问题的一个子集。模拟费用流方法的适用范围没有它的两个超集广，但是效率却远远高于这两种普适方法。

模拟费用流方法是指利用除费用流以外的手段解决一些费用流问题。一般来说，一个问题如果使用模拟费用流算法来解决，你在整个代码中不会见到任何一个与费用流有关的片段。可以说，这个方法非常的抽象。

在将问题抽象为线性规划模型后，我们可以无脑单纯形、内点法，也可以尝试用网络和流量描述这个问题，就可以使用费用流算法。如果这个问题还可以进一步转化为类似 “带权匹配” 这样的问题，就可以考虑模拟费用流了。

在模拟费用流问题的分析上，我个人常用的方法分为以下几种：

• 观察 Dp 方程
• 观察流量网络
• Dp 方程的二维直观表示
• 括号序列与折线法
• 单调性和凹凸性分析
• 匹配

一般来说，这些方法结合分析可以让问题变得简单。在解决问题的过程中，每一个步骤都有着一个更合适的分析方法，而分析出了一些结论或者性质后，不同的方法之间又能产生很多优美的等价关系。这种分析的过程也可以给解决其它问题带来灵感。

模型 1

一个兔子必须进一个洞，一个洞最多进一个兔子。兔子只能往左走。最小化兔子行走的距离之和。

这个问题可以结合括号序列分析。将所有兔子，以及最终有兔子进去的洞拿出来，不难发现，对于这些元素的任何一个前缀，兔子总不会比洞多。因此可以将洞看成左括号，兔子看成右括号。那么如何最小化距离之和呢？聪明的同学肯定已经看出来了，但是我们还可以换种方法。

在一个二维平面上，有自左向右延伸的一条折线。折线每经过一个洞可以选择高度加一或者不变，每遇到一个兔子高度必须减一。折线最终的高度必须为 0，且折线不能低于坐标轴。最小化折线下方的面积。

不难发现，上面两种分析方法是等价的，和原问题亦是等价的。

其中第二个思路非常直观，显而易见，我们只需要贪心地让折线尽量不上升即可。当遇到一个兔子，意味着折线在之前必须有一个地方上升，那么贪心选取最靠右的一个即可。

由于我们遇到的洞的位置单调递增，对于每个兔子，为它分配剩余的最靠右的洞即可，因此这个问题已经可以用一遍排序和一个栈解决。

模型 2

一个兔子必须进一个洞，一个洞最多进一个兔子。兔子只能往左走，洞有附加权值。最小化兔子行走的距离及选择的洞的权值之和。

这个问题较上一个问题的不同之处在于附加权值。我们可以建立新的模型描述这个问题，也可以尝试推广上一个模型。

如果去推广上一个模型，我们可以给折线的每次上升和每次下降赋权。令 $x$代表兔子或者洞的位置，$v$代表洞的附加权值，则一个洞 (折线的上升) 的权值可以表示为 $-x_i+v_i$，而一个兔子 (折线的下降) 的权值可以表示为 $x_i$。在合适的地方让折线上升或者下降，就能最小化权值总和。

除了洞的权值不再像模型 1 中那样递增之外，没有任何其它区别。我们只需要一个可以动态维护最小值的数据结构就可以解决。

模型 3

一个兔子必须进一个洞，一个洞最多进一个兔子。兔子可以向两边走，洞有附加权值，最小化兔子行走的距离及选择的洞的权值之和。

这个问题依旧可以用折线法分析，只不过会比较麻烦。我们再试试新的方法，比如匹配。

像上一个模型一样，我们将这些所有的兔子和洞都定义一个权值，做最小权最大匹配。

建立费用流模型。我们依次从每一只兔子开始增广，每一种可能的增广路实际上都对应着一个可以感性理解的事件：

从左往右观察每一只兔子和每一个洞。假设对于所有观察过的兔子和洞，我们都已经机智地按最优策略将它们匹配。由于每只兔子都需要进洞，当我们看到一只兔子，我们可以强行给它一个最好的洞 (如果没有洞的话，假设一开始无穷远处有无数个非常差的洞)。看到一个洞，我们可以考虑用它去替换一个非常差的洞。我们看到一只强势的兔子，它还可以抢之前兔子的洞，让之前的兔子去选择较差的洞，但是只要这么做可以让总权值变小，我们还是可以容忍这种行为的。如果考虑了这三类事件是否发生，我们已经可以保证，再添加了这个新的兔子或洞后，所有东西还是按照最优策略匹配的。

然后，我们再尝试用数字去描述每一种事件。一个兔子，不管它通过什么方式找到了一个洞，这个洞对于它来说不会有任何差别，但是不同的洞对权值和的贡献不一样。甚至，如果这个洞是抢来的，还需要考虑影响到的其它很多兔子匹配权值的变化。但是，我们给这只兔子所有能搞到的洞一个对应着总权值增量的权值，根据费用流的贪心性质，我们当然是选择权值最小的洞。

令 $v_i$为某种方式得到一个洞的权值，$w_i$为某种方式得到一只兔子的权值，$x_i$为兔子的坐标，$y_i$为洞的坐标，$s_i$为一个洞的附加权值。

• 一只兔子 $b$如果选择洞 $a$，总权值的增加量即为 $v_a+x_b$。之后一个好洞 $c$替换这个坏洞时，总权值又会增加 $s_c+y_c-v_a-2x_b$，对于好洞 $c$来说，它找到了一只兔子，并且产生了 $s_c+y_c-v_a-2x_b$的贡献，因此我们可以新增加一只权值为 $-v_a-2x_b$的兔子。
• 一个洞 $b$如果找到了兔子 $a$，总权值的增加量 $w_a+y_b+s_b$。之后一个兔子 $c$抢走了这个洞时，总权值又会增加 $x_c-w_a-2y_b$，对于 $c$来说，它找到了一个洞，而 $a$也不会因此无家可归，因为当我们处理 $a$的时候，我们肯定为它分配了在它前面的洞，后来 $b$找到了 $a$，现在 $b$把 $a$赶走了，$a$显然可以回去找之前分配给它的洞，赶走里面住的兔子，以此类推。这样，一切又回到了 $b$没有发现 $a$时的模样，因此，对于 $c$来说，我们可以新增一个权值为 $-w_a-2y_b$的洞。
• 一个洞 $b$如果找到了兔子 $a$，总权值增加量 $w_a+y_b+s_b$。之后一个新的洞 $c$替代了 $b$，总权值又会增加 $y_c+s_c-y_b-s_b$，对于 $c$来说，它找到了一个权值为 $-y_b-s_b$的兔子，因此我们新增一个这样的兔子。

这时，兔子已经不在是兔子，洞也已经不再是洞了。洞和兔子因为彼此的利益关系交织在一起，但是无论如何，我们只需要一个堆就可以把它们处理地服服帖帖的。

说了这么多，我们实际上是通过新增 “洞” 和 “兔子” 完成了两者的 “反悔” 操作。

模型 4

兔子和洞都有分身 (即一个位置上可以有多个洞和兔子)，一个兔子必须进一个洞，一个洞最多进一个兔子。兔子可以向两边走，洞有附加权值，最小化兔子行走的距离及选择的洞的权值之和。

如果已经理解了上一个模型，这个模型其实就是在记录权值的同时记录一下数量，对于一大批相同的兔子和洞，批处理完成匹配和反悔操作。同样还是用两个堆去维护这些东西的最小值。

但是，我们还不知道这样会不会因为不停新建新的兔子和洞导致复杂度爆炸。

实际上，如果你保证新建的节点数不比销毁的多，或者每次多的倍数不超过一个有限大的常数 $c$，而且销毁节点的次数为 $O(N)$，根据势能分析，总复杂度还是 $O(cN\log cN)$的。对于模型 4 时间复杂度的具体证明，此处从略。事实上陈江伦在冬令营上的讲课中也没有证明这个复杂度。

模型 5

树上的兔子要进树上的洞。一个兔子必须进一个洞，一个洞最多进一个兔子。兔子可以向两边走，最小化兔子行走的距离之和。

在树上，我们依旧需要完成所有的反悔操作。在树上，我们只能自底向上合并子树中的兔子和洞。

这就会有问题，由于每个遇到的兔子在任意时刻都需要有一个匹配的洞，我们就需要为那些无家可归的兔子先分配一个权值为 $+\infty$的洞。这个洞是不能被抢走的，也就是说我们不能将这个洞加入反悔序列内。如果它被抢走了，这只兔子就真的无家可回了。

我们依旧用堆维护子树内的权值最小的兔子和洞，将两棵子树内的兔子和洞完成匹配后，将堆合并即可。