首页 > 笔记 > 有上下界的网络流总结

有上下界的网络流总结


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

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

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的博客,我是从这学的。。

例题等等再放。。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×