重新总结下带上下汇的网络流的解法

    技术2022-05-19  34

    具体的解法参照的是北大课件的,只是总结一下,复习一下

     

     

    有流量下界的网络最大流

     

    如果 流网络中每条边 e 对应两个数字 B(e) C(e), 分别表示该边上的流量至少要是 B(e) ,最多 C(e), 那么,在这样的流网络上求最大流,就是有上下界的最大流问题。 这种网络不一定存在可行流   —思路:将下界“分离”出去,使问题转换为下界为0的普通网络流问题。   将原弧(u,v)分离出一条必要弧:  由于必要弧的有一定要满的限制,将必要弧“拉”出来集中考虑 添加附加点x,y。想像一条不限上界的(x, y),用必要弧将它们“串”起来, 即对于有向必要弧(u, v),添加(u, x)(y, v),容量为必要弧容量。 这样就建立了一个等价的网络。 去掉边(x,y),添加由ts的容量为正无穷大的边,使yx分别成为新的源和新的汇。  

    若此图上的最大流能够占满与Y相连的所有边的容量(自然也就会占满所有连到x的边的容量),

    那么原图上就存在满足上下界条件的可行流 

    对原图上的满足上下界条件的可行流进行增广,直到找到最大流。

    增广的过程中,对于必要弧不能退流(添加反向边)。

                    

    最新回复(0)