有上下界的网络流总结

本来想转载个来，但是学会了后感觉还是很水的，就随便写写。。

其实就是从一个基础的扩展了很多其他的。。

1.有上下界无源点汇点的可行流问题

这是最基础的。可行流是什么呢？就是在一个流量网络里面满足出入流相等，有一圈循环的流。因为没有源点汇点，所以所有的点都满足出入流量相等。

因为是可行流，所以只要随便有一条流就能满足了。

现在我们对于每条边都有个上下界的限制，就变成了有上下界无源点汇点的可行流问题。

这问题该怎么解决呢？我们想去掉下限，那么就修改原图中每条边的流量下界为0，上界为原上界-原下界。

这样其实就相当于对于每条边流了相当于它下界那么多的流量。这就很有问题了，每个点的出入流量不相等，那么我们就考虑把这个流量补上。先想下现在边的流量是多少：

现在图中一条边i将x的流量汇入点a，实则汇入x+low[i]的流量（low[i]为i的下界），于是应当有额外一条low[i]的边连入a
现在图中一条边i将x的流量运出点a，实则运出x+low[i]的流量（low[i]为i的下界），于是应当有额外一条low[i]的边自a连出

由于这些额外的流量在图里面没有，所以所有连入原图的边应当自一个额外的源点出发，设为S’，同理，应当有一个额外的汇点，设为T’

然后，跑S’到T’的最大流。为什么要最大流呢？因为假如某条额外加边跑满流量了，原图就合法了啊。。原图中每条边的可行流是它在现在图中对应边的流量加它的下界

这样发现某个点会有很多连向源汇点的额外边，就可以把它们和成一条边。而且连向源点的额外边和连向汇点的额外边还可以抵消。这样我们把额外边的数量就限制成了严格O(n)的了。

2.有上下界无源点汇点的最小费用流问题

就是上面的加上最小费用的限制。

第一思路就是直接在原图上跑最小费用最大流，把所有的额外边加上它们原来的边的费用。这样其实就是正确的了。。

但是我们一想，额外边是限定满流的，那么它的费用其实就是个常数了。这样只用在原图上加费用，跑完加上就行了。这样还可以用上面的建图优化。

3.有上下界多个有限源汇点的可行流问题

有多个有限源汇点。。其实就是字面意思，有些点需要消失一些流量，有些点需要产生一些流量。

对有限源点（额外产生流量），从S’连一条上限为x的附加边；
对有限汇点（额外消失流量），向T’连一条上限为x的附加边；

4.有上下界多个有限源汇点的最小费用流问题

就在上面的基础上跑最小费用。。

5.有上下界一组无限流量源汇点的可行流问题

也是字面意思，多了源汇点。。

我觉得这个非常巧妙，直接从汇点往源点连一条流量inf的边就成了第一个问题了

（我问DP这个思想是不是他想出来的，他说这是先人的智慧，是我们的祖先那伟大劳动人民的思想的结晶：早在大禹治水的时候，他就睿智的对部下说：你从海里往源头连一条边，就能跑出有上下界一组无限流量源汇点的可行流了

6.有上下界一组无限流量源汇点的最小费用流问题

在上面的加上费用就行了

7.有上下界一组无限流量源汇点的最大流问题

这里要求最大流。。

我们首先跑出一个可行流，但是这不一定是最大流。但是我们发现一个性质，当我们采用增广路算法求解最大流时，并不会修改源点到汇点路径之外的边的流量大小。

这意味着当我们第一次跑出一组可行解之后（跑这组可行解，即跑从S’到T’的最大流），直接在现在的图上直接跑S到T的最大流，首先不会影响被视作原图中边流量下界的边的流量情况——他们依然是满流的，而且图上连的T->S的边的退流过程，等价于有一条S->T的边在增广，于是还把第一次可行流的答案加入第二次跑出的最大流中。也就是说，这时跑出来的最大流可以被认为是满足上下界前提下的最大流。

要是要求流量最小怎么办？从T开始跑最大流，用可行流减下就好啦

7.有上下界一组无限流量源汇点的最小费用最大流问题

直接在上面加上费用就好了。。

安利一波DP的博客，我是从这学的。。

例题等等再放。。