上下界费用流学习笔记

前言

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

下面整理一下网上的blog

前置知识

最小费用最大流

正文

最简单的一类：

无源汇上下界可行流

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

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

建图方法

我们可以考虑建一个新图。
首先弄一个新的源点和汇点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

上下界费用流学习笔记

原文：https://www.cnblogs.com/leason-lyx/p/11144527.html