模拟费用流

感性理解

Posted by ShanLunjiaJian's Blog on August 21, 2021

本文仅作存档,请阅读 讲稿索引/网络流相关问题选讲。

照抄command_block《模拟费用流小记》。

用\(u\stackrel{f,c}{\longrightarrow}v\)表示从\(u\)向\(v\)连容量为\(f\),费用为\(c\)的边。如果国际惯例是费用在前请D爆我/ll

路径中用\(\rightarrow\)表示顺着边流,\(\leftarrow\)表示逆着(退流)。

由于类似于二分图的网络流模型占了大部分,我们用\(i\)表示第\(i\)个左部点,\(i^\prime\)表示第\(i\)个右部点。


模拟费用流是什么

呃,大概就是利用费用流来枚举所有可能的反悔贪心策略。


经典套路

  • 直接用数据结构支持找最短路,这个做法可以同时支持最大流和不必最大流的问题。

  • 根据费用流凸性,用wqs二分去掉 流量为\(k\) 一类的限制。

  • 按一定顺序加边加点,考虑新出现的增广路和负环,这个做法只支持不必最大流的问题。


经典结论

如果不加边加点,从\(s\)发出或指向\(t\)的边不会被退流,因此我在某些地方书写的时候会省略\(s,t\)。

增广路不会经过一个点多次。


让我们从简单题开始吧(

NOI2019 序列

两个长\(n\)的序列\(a,b\),你需要选出\(k\)对\((i,j)\),其中有\(l\)对满足\(i=j\),最大化所有选择的\(a_i+b_j\)的和。\(n\leq 10^5\)。

不光题意,这题的建图大家想必都耳熟能详了(

我们建立两排点\(i,i^\prime\),先连\(s\stackrel{1,a_i}{\longrightarrow}i,i\stackrel{1,0}{\longrightarrow}i^\prime,i^\prime\stackrel{1,b_i}{\longrightarrow}t\),为了表示有\(k-l\)对可以自由选择再连\(i\stackrel{1,0}{\longrightarrow}u,u\stackrel{k-l,0}{\longrightarrow}v,v\stackrel{1,0}{\longrightarrow}i^\prime\)。跑最小费用流,增广\(k\)轮即可。

然后开始考虑所有增广路的形态。经典结论指出,从\(s\)出发或指向\(t\)的边不会被退流,这说明一旦选择了一个\(a_i\)或\(b_j\),以后一定仍然选择它。

同时经典结论还指出,增广路不会多次经过同一个点,而这个图里面不经过\(u,v\)的话路径数量少的可怜,\(u,v\)又都只能经过一次,所以现在我们可以开始枚举所有增广路了。

为了方便,我们称一个已经配对的点是随意的,当且仅当它和对面不与它对应的点配对;否则它是不随意的。

你发现一共只有如下几种,分别对应几个反悔贪心策略 :

  • 不经过\(u,v\)

    • \(i\rightarrow i^\prime\),意义是直接选择一对相等的
  • 经过\(u,v\)中一个

    • \(i\rightarrow u\leftarrow j\rightarrow j^\prime\),意义是对于\(i,j\),如果\(j\)之前是随意的并且和\(k^\prime\)配对,我们加入\(i,j^\prime\),把\(j\)变成不随意的,把\(i\)变成随意的与\(k^\prime\)配对

    • \(i\rightarrow i^\prime\leftarrow v\rightarrow j^\prime\),意义是对于\(i,j\),如果\(i^\prime\)之前是随意的并且和\(k\)配对,我们加入\(i,j^\prime\),把\(i^\prime\)变成不随意的,把\(j^\prime\)变成随意的与\(k\)配对

  • 经过\(u\rightarrow v\)

    • \(i\rightarrow u\rightarrow v\rightarrow j^\prime\),意义是直接选一对随意的

    • \(i\rightarrow i^\prime\leftarrow v\leftarrow u\leftarrow j\rightarrow j^\prime\),意义是对于随意配对的\(i,j^\prime\),加入\(i^\prime,j\)凑成两对不随意的

。每一种都可以用堆维护,所以开两车堆就做完了。具体的,这两车堆分别维护

  • 没有选的最大的\(a_i\)

  • 没有选的最大的\(b_i\)

  • 对于选了的\(a_i\),最大的\(b_i\)

  • 对于选了的\(b_i\),最大的\(a_i\)

。复杂度是\(O(n\log n)\)。

如果你发现可能的增广路实在是少的可怜,就可以考虑这个题的方法。


PA2013 Raper/CF802O April Fools’ Problem (hard)

你要生产\(k\)个蛋白质,每个蛋白质都要先在核糖体进行挤压,再到高尔基体涂上反光层。每天每个细胞器都只能加工一个蛋白质,并且每天的ATP消耗量可能是不同的。现在你知道接下来\(n\)天两个细胞器分别的ATP消耗量序列\(a,b\),求最小代价。\(n\leq 10^5\)。

建图很简单,每天建一个点分别跟\(s,t\)连代价,然后往下一天连即可。当然要跑流量是\(k\)的最大费用流。

一个做法是wqs二分去掉\(k\)然后模拟费用流。

考虑这里增广路可能非常多,所以我们尝试按某种顺序加点吧。

从前往后还是从后往前?都试一下好了(

还是算了。我们从后往前加,这样新加入的蛋白质可以匹配的高尔基体集合是越来越大的。

考虑加入点\(i,i^\prime\)之后可能出现的增广路和负环,你发现

  • 增广路只有一种,是\(s\rightarrow i\rightarrow j\rightarrow t\),意义是直接选一对新的

  • 由于再怎么说还是二分图,并且只有\(s,t\)的邻边有流量,负环少的可怜,只有三种 :

    • 经过\(s\)的\(s\rightarrow i\rightarrow j^\prime\leftarrow k\leftarrow s\),意义是把之前的匹配\((k,j^\prime)\)改为\((i,j^\prime)\)

    • 经过\(t\)的\(i\rightarrow j^\prime\rightarrow t\leftarrow k^\prime\leftarrow i\),意义是把之前的匹配\((i,j^\prime)\)改为\((i,k^\prime)\),因为我们还没给\(i\)匹配呢,不可能真的存在这样的负环

    • 同时经过\(s,t\)的\(s\rightarrow i\rightarrow j^\prime\rightarrow t\leftarrow k^\prime\leftarrow l\leftarrow s\),意义是把之前的匹配\((l,k^\prime)\)改为\((i,j^\prime)\),这个可以不考虑,因为它是一条\(s\rightsquigarrow t\)加上一条\(t\rightsquigarrow s\),而前者我们已经考虑了,后者肯定是增广过的所以跑回去一定不优,否则当初就不会跑了

然后我们就用堆维护两种贪心策略就好了。具体地,开两个堆,分别维护

  • 没有匹配的\(i^\prime\)

  • 已经匹配的对\((i,j^\prime)\)中的\(i\)

然后就做完了。复杂度是\(O(n\log^2 n)\)。这个启示我们,如果有个流量是\(k\)的限制,可以把它wqs二分掉。

另一种做法是直接使用线段树维护最优的增广路。我们可以从分治的角度考虑,这个最短路如果跨过中点,可以用两边的信息拼出来,否则可以递归两边。

怎么拼呢?我们需要支持操作 :

  • 全局最短增广路

  • 单点修改(把已经选过的点权改为inf)

  • 区间修改反向边流量

实际上增广路只有两种,也就是从左往右和从右往左的。

  • 从左往右的始终可行。

  • 从右往左的要求中间的反向边都至少有\(1\)的流量。

只需要维护9个信息,容易知道它们的合并方式 :

  • \(a_i,b_i\)的最小值 : 废话

  • 从左往右的最短路,同时也是从左往右的最短增广路 : 左右儿子的这个信息,和左儿子\(a_i\)最小值加上右儿子\(b_i\)最小值中取\(\min\)

  • 从右往左的最短路 : 同上

  • 从左往右的流量(也就是从右往左的容量)及其加法标记 : 这个东西合并就是取\(\min\)

  • 可以接收右边流过来流量的最小\(b_i\) : 如果右儿子不能从右往左流,是右儿子的这个信息,否则是左右儿子的这个信息取\(\min\)

  • 可以往左流的最小\(a_i\) : 同上

  • 从右往左的最短增广路 : 左右儿子的这个信息,和左儿子可以接收右边流过来流量的最小\(b_i\)加上右儿子可以往左流的最小\(a_i\)取\(\min\)

复杂度一个\(\log\)。


UER8 雪灾与外卖

这个题做法是有问题的。

数轴上有\(n\)个送餐员和\(m\)个餐馆,坐标序列分别是\(x,y\),每个餐馆\(i\)有\(c_i\)道菜,价格都是\(w_i\)元,送餐员\(i\)到餐馆\(j\)取餐需要花费\(\vert x_i-y_j\vert\)元,求让每个送餐员都取到一道菜的最小花费。\(n,m\leq 10^5,v\leq 10^9\)。

现在已经是346 downvote了/jy

简直是,堆优化自由匹配问题的集大成者。题解中给出的几个部分分结论非常经典。

直接建模很简单,建一个数轴即可。注意这个图并不是二分图。为了去掉 所有送餐员都取到一道菜 的限制,给每个送餐员\(-\infty\)的费用。

注意到这么一个性质 : 匹配不会交叉,也就是说数轴上按顺序排列的\(i^\prime,j,k,l^\prime\)如果是\((i^\prime,k),(j,l^\prime)\)这样匹配,中间被多走了两遍,显然不如\((i^\prime,j),(k,l^\prime)\)优。

这给出了一个非常强的限制 : 如果我们从左往右处理

那就从左往右加入点,考虑所有可能的增广路和负环 :

  • 如果加入了一个送餐员\(i\)

    • 增广路有\(s\rightarrow i\rightarrow j^\prime\rightarrow t\),意义是找一个左边的餐馆匹配

    • 负环有\(s\rightarrow i\leftrightarrow j\leftarrow s\),意义是找一个手里有菜的送餐员,把他的菜抢过来

  • 如果加入了一个餐馆\(i^\prime\)

    • 增广路有\(s\rightarrow j\rightarrow i^\prime\rightarrow t\),意义是找一个左边的送餐员匹配

    • 负环有\(i^\prime\rightarrow t\leftarrow j^\prime\leftrightarrow i^\prime\),意义是找一个送出去菜的餐馆,抢它的生意

。然后考虑它们的代价,这里就不像上面那么简单了 :

  • 如果加入了一个送餐员\(i\)

    • 找一个还有菜的餐馆\(j^\prime\)匹配,代价是\(x_i-y_j+w_j\)

    • 找一个有菜的送餐员\(j\),把他的菜抢过来,代价是\(x_i-x_j\)

  • 如果加入了一个餐馆\(i^\prime\)

    • 找一个没有菜的送餐员\(j\)匹配,代价是\(y_i-x_j+w_i-\infty\)

    • 找一个送出去菜的餐馆\(j^\prime\),抢它的生意,代价是\(y_i-y_j+w_i-w_j\)

。现在可以爆力开堆了,用两车堆维护

  • 没有菜的送餐员的\(-x_i\)

  • 有菜的送餐员的\(-x_i\)

  • 还有菜的餐馆的\(-y_j+w_j\)

  • 送出去菜的餐馆的\(-y_j-w_j\)

注意到菜可能很多,所以我们需要在堆里面记一个菜的数量。


NOI2017 蔬菜

题目怎么跟我同名啊/kk

有\(n\)种菜,其中第\(i\)种单价是\(a_i\),有\(c_i\)个,第一次卖出还可以额外获得\(s_i\)的钱。每个菜都有变质时间,第\(i\)种菜有一个值\(x_i\),表示这种菜有\(x_i\)个会在第一天结束时变质,有\(x_i\)个会在第二天结束时变质……最后可能不足\(x_i\)个在\(\lceil\frac{c_i}{x_i}\rceil\)天结束时变质。每天你可以卖\(m\)个菜,多次询问卖\(p\)天最多可以获得多少钱。\(\)

变质 听起来就很离谱,我们时间倒流,变成每天会出现一些菜,这就很好。

咕咕咕。