《浅谈 OI 中的模拟费用流问题》第四节读后感（简称：中译中）

· · 个人记录

注：这并不是正常的模拟费用流部分，而是模拟费用流在一些特殊图上特殊维护方式。（其实就是复读了一下22年《浅谈 OI 中的模拟费用流问题》第四节的有关内容）

声明：本人水平很低，尤其是在贪心和网络流方面，所以下面写的很大概率会出错，这篇文章只是写给自己看的。

1.老鼠进洞问题的三种解释

跳伞求生

省流：n 个老鼠，m 个洞，每个老鼠有个位置 a_i，洞有位置 b_i 和收益 c_i，老鼠只能进自己右边的洞，一个洞只能进一个老鼠，老鼠 i 进洞 j 的收益为 a_i-b_j+c_j，最大化收益。

这个题也算是模拟费用流中很经典的一集了，我们知道这道题有如下做法：

将老鼠和洞按位置大小排序，然后开个堆扫一遍，对于一个洞就把 -b_i+c_i 放进堆里，对于老鼠就把堆顶元素拿出来，如果收益大于 0,那就把收益加到答案，然后把 -a_i 扔进堆里。

对于这个算法，我们能提出三种解释：

I.反悔贪心（by 0htoai）： 考虑对于每个老鼠有两个选择，匹配之前一个洞，或者把某个已经匹配了洞的老鼠挤下去自己进这个洞，因此 -a_i 扔进去是拿来反悔的。注意到挤掉别的老鼠这个事情不会引发连锁反应的原因是贡献是可加的，因此如果引发了连锁反应，那么不如直接让当前老鼠和连锁反应最后面那个匹配，这是等效的。

II.维护折线： 首先我们建出一个 naive 的建图。

这个建图本身无需多说，S 到链上一条边代表一个老鼠，链到 T 代表一个洞

这里我们需要先发现一个事情，那就是老鼠和洞其实是等效的，就是说一只新的老鼠 i 退流掉一个老鼠 j（设其对应洞 k） =这只新老鼠 i 匹配一个洞，这个洞的代价为 -a_j-b_k+c_k。

换而言之是什么呢，我们没有必要真的去退流，当一只老鼠匹配一个洞以后，我们可以直接新加一个洞，代价见上。

这个时候通过线段树已经可以解决问题了，但这不是我们想要的上面那个优美的算法，所以，我们，进行一个 dp。

这个 dp 的原理是，观察到一个流在链上是往大的方向走的，走到某个到 T 的边，因此我们从小往大 dp，设 f_{i,j} 表示当前走到链上第 i 号点，还有 j 的流量还没匹配此时最大的收益。

1.如果当前位置添加了一只老鼠：

f_{i,j}=max(f_{i,j-1}+x,f_{i-1,j}) f_{i,0}=f_{i-1,0}

费用流的凸性是我们优化这个 dp 的关键，设 g_{i,j}=f_{i,j}-f_{i,j-1}，那么 g_{i,j} 随 j 单调递减。

换而言之，f_{i,j} 的 \max 可以被改写：

f_{i,j}=f_{i,j-1}+x (j\neq 0,x\ge g_{i-1,j}) f_{i,j}=f_{i-1,j}(j \neq 0,x < g_{i-1,j})

既然知道了 f_{i,j} 和 g_{i,j} 的关系，那么 g_{i,j} 同样可以由 g_{i-1,j} 来表示：

g_{i,j}=g_{i-1,j}(g_{i-1,j}>x) g_{i,j}=x (g_{i-1,j-1}> x,g_{i-1,j}\le x) g_{i,j}=g_{i-1,j-1}(g_{i-1,j}\le x)

这等价于什么呢，如果我们只维护 g_{i,j} 的话，g 就是一个堆，从 i-1 到 i 相当于加入一个 x 进堆。

2.如果当前位置加了一个洞

同样的推导过程，可得在这种情况下，等价于删除 g_{i-1,1} 之后加入 -x，同时 g_{i-1,1} 会加到 f_{i,0}——也就是最终答案中。

那么，就会发现，这个维护的过程居然和上面的算法流程是一模一样的！

（貌似上面部分的老鼠和洞全部写反了，悲！！！主要就是推导的思想没问题就行了，不要看细节啊！！！我懒得改！！！）

III.模拟费用流.其之二： 这个想法的核心还是洞和老鼠的转化。

考虑每加一个洞或者老鼠就跑一次费用流，维护其残量网络，注意到因为按顺序添加，后面的洞肯定能匹配前面的老鼠，后面的老鼠匹配不了前面的洞，因此只要把所有洞都变成老鼠，那后面来的洞就可以匹配前面的所有了，这是等价的，而洞改成老鼠，实质上就是之前反悔的过程。

事实上，这里需要注意到的一件事情是，我们这样维护的一个原因是我们无需关心链上的流量，因为按顺序添加最后的洞是一定能匹配所有老鼠的（这个在后面的例题中还会说到）

2.第三种解释的一些延伸

事实上，第三种解释所强调的核心思想是很利于维护更多东西的，让我们再重复一遍：首先是维护残量网络，然后是老鼠和洞转化。下面举若干例子。

（P.S：在原论文中这些例题被归为一类，叫做“单向链”）

1 带修

上面的问题，但是带修，要支持在链首或者链尾增加老鼠/洞。

（u1s1，这一部分我只能说是能说服我自己，不知道对不对，因为这个题事实上是论文作者自己编的......）

还记得第三种解释中我们提到，在最后面添加洞是无需关心链上的流量的，其实分析一下会发现，在最前面添加洞的话跟流量也没有什么关系，因为压根这个洞谁都匹配不了。老鼠的话同理，这样一来，我们还是不关心链上的流量问题，那么其实和上一道题是一样的：我们开两个堆维护当前的老鼠/洞，末尾加老鼠/前面加洞就加进对应堆，另外两个就是从堆顶取元素。

2 区间询问

上面的问题，但是区间询问。

从这里开始，一些题目会涉及到跟数据结构的结合，但至少在本节内都还是这个费用流模型......

区间询问的话可以考虑分治，每次只考虑跨过中点的询问，如果暴力做的话可以直接以中点为起点做两边加洞/鼠的版本（上一题）但这样为啥不去写暴力呢

费用流的凸性，我们可以知道（换句话说，不会证）答案关于中点那条边的流量是个凸函数，因此具有可三分性，因此我们可以使用可持久化数据结构维护中点开始每个前缀后缀的残量网络，支持查询 k 大等操作即可。

3 蔬菜

这个题太著名了，先略过。

3.线段树维护单项链流量

在之前的两道例题中，我们一个共同点是没有关心链上流量的问题，但事实上并不是所有题都是这样，这里有两个单项链的例子。

老鼠进洞的第四种解释

事实上，老鼠进洞那个题还有一种做法，使用线段树维护链上每条边的反边的流量，由于老鼠和洞可以互相转化，因此每有一只老鼠满流就把老鼠变成洞，这样是不会出现负环的，现在考虑增广，一只老鼠只能沿着平行边走去匹配一个洞，在线段树上知道它能走到哪里是容易的。然后增广的话，取的老鼠变成洞，洞变成老鼠，那么流量就是在线段树上区间+1 -1。

例题

咕了。

对于前三节的内容（对应论文4.1）总结一下来说，我们探讨了一类老鼠进洞模型及其变体，以及对其的三种维护方式。

这类老鼠进洞的问题具有如下特点：

而常见的三种维护方式：

4.双向链

双向链即是在单向链的基础上，添加了 (i+1,i) 的边，这种情况下我们无法忽略链上的边权（事实上在单向链中我们是通过类似前缀和的东西使链上没有边权，显然这里不能这么做）。比如下面这道题：

老鼠进洞.改

同样的，我们利用上面的几种维护方式（这里就需要说到直接考虑用堆维护的局限性了，事实上，我们只能从维护折线的角度出发得到这样一个和用堆维护本质一样的做法） **线段树维护流量** ~~对不起，但是我真没看懂他在说什么B话。~~ 感谢贾老师，这下看懂了。 因为是线段树，所以没必要一边加洞一边加老鼠，考虑先把所有洞都加进去，现在我们是按顺序加老鼠，然后用线段树模拟增广。 考虑这么一个事情：因为是按顺序增广，之前的老鼠要么往前要么往后，往前的话，和后面加进来老鼠的路径莫得交集（这里需要注意到因为费用计算的原因，两个匹配间是不交的）。 这样的话这里有个显然的事情：就是一个老鼠往前走肯定是不会受到阻碍的，往后的话，对于小于自己位置的链上的边，他们的流量就只能往前流了，换句话说 $k<i$ 的 $(k+1,k)$ 的反向边一定流量一直增大，这个听起来像废话，实际上很有用，我们考虑怎么维护 $i$ 到 $j$ 的最短路，设链上第 $i$ 条边往后流量 $x_i$，往前 $y_i$，那么根据刚才的事实有： $i\le j$： 最短路就是 $\sum_{k=i}^{j-1} x_k **维护折线** 这位更是重量级。让我们稍稍回忆一下第一节中的 dp，然后我们就可以设 $f_{i,j}$ 有如下含义，当 $j>0$ 时表示有 $j$ 个洞需要匹配老鼠，$j<0$ 时表示有 $-j$ 个老鼠需要匹配洞。 那么转移方程是容易得到的，这里我选择抄 ppt！ ![](https://cdn.luogu.com.cn/upload/image_hosting/htq02ezd.png) **维护方法.其之一（直接维护 $f$）** 这个是刚刚翻 laofu ppt发现的做法，事实上这个也适用于刚刚单向链的弱化版。 就是，思考差分数组只加了一项实际为我们带来什么，事实上这说明只有一个位置需要决策，剩下位置是整体位移+整体加某个值，这个是容易打标记处理的事情，因此就可以 $O(n)$ 做了。 （但是注意到这种做法里面，是不能让洞有额外的收益 $c_i$ 的？） 另，对这个方法进行改进，可以得到当费用与流量关系更复杂的情况。 **维护方法.其之二（维护折线）** 这个地方洞和老鼠的维护本质一样，只说洞的维护方式。 设 $f(j)$ ，含义同上。 那么跟上面一样的有递推式： $f(j)=min(f(j),f(j+1)+c+x) j\ge 0 f(j)=min(f(j),f(j+1)+c-y) j<0

注意到这里 f 本身不凸，但是 f(j) 中 j<0 和 j>0 的部分各自单独是凸的。所以对着两部分分别做差分得到 G_0 和 G_1，这两个可重集内部单调。

进行一个分类讨论：

1.f(0) \le f(1)+c+x

那么新的 f(0) 是不变的，而 g(1)\ge-c-x 可以推的 G_1 也不变。对于 G_0 部分则是类似单向链那部分，最后就是在 G_0 加一个 c-y。

2.f(0) > f(1)+c+x

那么新 f'(0)=f(0)+g(1)+c+x

此时类似单向链的推导方法，可以得到 G_1 是删 \min 后加入 -c-x。

同时我们要构造一个函数 h(j)=f(j)+|j|\times x，这个函数是凸的。

这个函数是凸的意味着 f(1)-f(0)+x\ge f(0)-f(-1)+y

即 f(-1)\ge f(0)-g(1)-x-y>f(0)+c-y.

那么之后就可以同理推得 G_0 是加入 -x-y-g(1)。

5.双向链的例题

维护线段树

雪灾与外卖：一模一样了属于是。

IOI2017 Wiring：居然还是一模一样！

CSTC2010 产品销售：强制进洞，这意味着没有办法进行反悔，也就是说我们得按顺序加洞和老鼠了，这种情况下反边加了可能删掉，但是加入和删除可以证明只会出现一次。

维护折线

6.扩展到树上

其实就是把原先的算法结合一些树上算法，有时间再更。