上下界费用流学习笔记上下界费用流学习笔记

上下界费用流学习笔记

前言

今天（2019.7.5）模拟赛出了一道上下界最小费用可行流的题目，我比赛的时候把想到了正解是费用流，然而并不会打上下界费用流（TOT），赶紧恶补一下上下界费用流

下面整理一下网上的blog

话说这玩意比splay还难调啊,供电网络调了一整个晚上都没调出来

好吧我忘记把一开始下界对答案的贡献加进去了

前置知识

最小费用最大流

正文

最简单的一类：

无源汇上下界可行流

首先，可行流的定义：一个网络网络中，存在一条流，满足任意点的总流入量等于总流出量（即流量守恒）。

在上下界可行流中，每条边的流量都要满足大于等于下界，小于等于上界

建图方法

我们可以考虑建一个新图。
首先弄一个新的源点和汇点ns和nt。
然后，对于原图中每条(u,v)的边，建u→v流量为up-down
然后，我们设一个d(x)表示x流入x点的边的下界和，减去流出x点的边的下界和。
当，d(x)>0则连ns→x流量为d(x)的边。
否则，d(x)<0则连x→nt流量为-d(x)的边。
我们不妨称后面这两条边为附加边。

流程

从源点流到汇点，当每条附加边已经流满的时候，则可以确定这个图可行。

By RainbowCrown

~cghtql%%%~

为什么这样建图呢？

首先要满足的条件就是每条边的流量达到下界，之后再考虑为了满足流量守恒而在不溢出上界的情况下增流的方案。

可以称原始的所有边恰好达到下界（若对某一边没有特定要求即为0）的不一定满足流量守恒的流称为初始流，为了满足流量守恒而进行的适当增广添入的流所先独立形成的一个流称为附加流。两者在同一个网络下合并起来即为所求可行流。

对于初始流，只需要根据给定条件强制加上即可，我们只需要考虑如何处理附加流。

很显然可以发现，因为初始流附加流合并后的网络流量守恒，所以初始流附加流对每一个点来说其实是互补的。若初始流上某一点流入量不等于流出量，便在附加流上弥补掉这个差。

By ccosi

就是说，首先强制让每一条边流down流量来满足下界，但这样显然不满足流量平衡，所以再考虑流一些附加流来满足流量平衡。由于不能超过上界，现在每一条边还剩下up-down的流量。若流入某个节点的流量大于流出的（d(x)>0），就从超级源向它连一条流量为d(x)的边，反之亦然。

为什么这样流可以使答案正确呢？

感性理解，因为如果从源到x连得那一条d(x)的边流满了，就说明从x流出去了d(x)的流量，那么先前不满足流量平衡，多出来的那一部分流量就被“消化”掉了。从x向汇连的边流满了，就说明缺少的那部分流量被补充了。

有源汇上下界可行流

建图方法：

从T向S连一条下界为0，上界为正无穷的边，然后像无源汇那样建图就好了

为什么呢？

感性理解，对于任意一个有源汇的可行流，都可以从T把总流量流回S以满足流量平衡。而对于一个每个点都满足流量平衡的图，就是无源汇上下界可行流的解决范围。

有源汇上下界最大流

先像上面一样跑一遍判断可行性

现在考虑跑完有源汇上下界可行流后的初始流附加流合并网络，可知若不考虑源汇点，是流量守恒的，那么把T->S的边拆掉（使s->t变成一个有源汇的网络流图），在附加网络上再求得残余网络的S−>T最大流，这个最大流除开源汇点也是流量守恒的，那么同样也是原图的一个可行流。同时又因为求得的是残余网络的最大流，已经达到了最大。所以答案即为可行流加上残余网络的最大流。

By ccosi

有源汇上下界最小流

求解方法

求ss->tt最大流
连边t->s,inf
求ss->tt最大流
答案即为边t->s,inf的实际流量

证明

第一遍做的时候并无t->s这条边，所以s->t的流量已经尽力往其它边流了

加上t->s这条边后，流过这条边的都是些剩余的流不到其他边的流量，从而达到尽可能减少T->S这边上的流量的效果，即减小了最终答案。

By Clove_unique

有源汇上下界最小费用可行流

建图方法

将有上下界的网络流图转化成普通的网络流图

首先建立附加源点ss和附加汇点tt
对于原图中的边x->y，若限制为[b,c]，费用为cost，那么连边x->y，流量为c-b，费用为cost
对于原图中的某一个点i，记d(i)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和
若d(i)>0，那么连边ss->i，流量为d(i)，费用为0
若d(i)<0，那么连边i->tt，流量为-d(i)，费用为0
连边t->s，流量为inf，费用为0

求解方法

跑ss->tt的最小费用最大流
答案即为（求出的费用+原图中边的下界*边的费用）

证明

注意：
有上下界的费用流指的是在满足流量限制条件和流量平衡条件的情况下满足流量限制条件和流量平衡条件的情况下的最小费用流
而不是而不是在满足流量限制条件和流量平衡条件并且满足最大流最大流的情况下的最小费用流
也就是说，有上下界的费用流只需要满足网络流的条件就可以了，而普通的费用流是满足一般条件并且满足是最大流的基础上的最小费用

证明同 有源汇的可行流

By Clove_unique

另一种连边方式

至此，上下界网络流的一些基本建图方法已经讲完了。
而且，经过我的一些观察，找到了两种建图方法——
一种是我上述的方法，在点少边多的图药效奇佳，而且好理性证明。
另一种是网上学到，在点多边少的图药效奇佳，但是我不会理性证明，只会很感性地理解。（画图）
在此口胡一下在“无源汇上下界可行流”的建图方法

建立超级源与超级汇。
对于一条边(u,v)，建从v→u流量为up-down的边。（注意是v→u）
然后建ns→v流量为down的边。
然后建u→nt流量为down的边。
之后直接求即可。
这个可以感性理解。
我们看到原来的u→v，由于下界是down，那么当这条边流过了down之后，相当于u失去down的水，v得到down的水，剩下的是up-down的水。

这样建图就可以模拟上述过程。

By RainbowCrown

其实我觉得都是一种东西啦

例题

供电网络

狸和桃子居住的世界里, 只有一个国家, 这个国家有很多城市, 每个城市直接由中央政府管辖.
电力是这个国家的唯一能源, 但是每个城市的发电能力都不一样, 于是就产生了某些城市电力不足, 而某些城市却电力过剩的情况.
阿狸作为国家的首席工程师, 阿狸的一项重要工作就是均衡整个国家的电力, 使得每个城市的电力都恰好没有剩余或不足.
好在一些城市之间有电线可以输送电力, 这些电线都有自己的输送上限和下限, 并且输送电力的同时会产生大量的热.
每条电线i 发出的热量一定是关于输送电量的一个没有常数项的二次函数,即a_ix^2+b_i*x, 并且由于电线是二极管做成的, 很显然只能单向输送电力. 每单位热量需要用1 单位的金币来冷却. 任何两个城市之间, 至多有一条电线.
不幸的是, 有时电力网络不像我们想的那么完美, 某些情况下可能无论如何都不能满足整个国家的电力需求. 这种情况下就只好向别的世界购买电力或者将电力输出给别的世界(注意, 每个城市的电力不能有剩余!), 每个城市买入或者输出电力的价格是不一样的(输出也要花钱).
由于阿狸的国家没有小数的概念, 输送,、购买或者交换电力都必须是以整数1 为单位.
阿狸的任务是最小化金币的花费(买入/送出的费用+电线上发热的冷却费用),他最近被这个问题搞得焦头烂额, 以至于没有时间去陪桃子玩, 结果天天被桃子骂T_T. 好在有你, 万能的程序猿, 请你编写一个程序来帮阿狸解决这个问题吧.

对于5%的数据满足m = 0.
对于30%的数据满足n <= 30, L = 0, a = 0.
对于60%的数据满足n <= 50, m <= 200.
对于100%的数据满足n <= 200, m <= 600, u != v, 1 <= u, v <= n, 1 <= a, b <=3, 1 <= L <= 10, 1 <= L <= U <= 100, 0 <= in, out <= 100, -5 <= left <= 5.

有源汇上下界最小费用可行流的模型

首先，有剩余left电力的城市x，S向x连一条上下界都为left，费用为0的边，表示它多出这么多电。而缺少-left电力的城市x，x向T连一条上下界都为-left，费用也为0的边，表示它还需要这么多电。

城市可以买入或送出电力，所以，S向每个城市连一条下界为0，上界为正无穷，费用为买入电的费用的边，每个城市再向T连一条下界为0，上界为正无穷，费用为送出电的费用的边

对于题目给定的电线，由于是一个二次函数，我们就把它拆成U-L+1条边，第一条边上下界都为L，费用为(L^2*a+L*b)，之后的边上界为1，下界为0，费用为a+b,3a+b,5a+b…

最后跑一下模板就好了

据说要动态开边，但我没开就过了