网络流 计算机学院.pptVIP

网络流 计算机学院 网络流问题 由于人类对自然资源的消耗，人们意识到大约在2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有n个太空站位于地球与月球之间，且有m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船i 只可容纳H[i]个人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4)表示该太空船将周期性地停靠太空站134134134…。每一艘太空船从一个太空站驶往任一太空站耗时均为1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。 网络流问题 ?? 由文件input.txt提供输入数据。文件第1行有3 个正整数n（太空站个数），m（太空船个数）和k（需要运送的地球上的人的个数）。其中 1=m=13, 1=n=20,1=k=50。接下来的n 行给出太空船的信息。第i+1 行说明太空船pi。第1 个数表示pi 可容纳的人数Hpi；第2 个数表示pi 一个周期停靠的太空站个数r，1=r=n+2；随后r 个数是停靠的太空站的编号(Si1,Si2,…,Sir)，地球用0 表示，月球用-1 表示。时刻0 时，所有太空船都在初始站，然后开始运行。在时刻1，2，3…等正点时刻各艘太空船停靠相应的太空站。只有在0,1,2…等正点时刻才能上下太空船。??将全部人员安全转移所需的时间输出到文件output.txt 中。如果问题无解，则输出0。 一些符号和定义 V表示整个图中的所有结点的集合. E表示整个图中所有边的集合. G = (V,E) ,表示整个图. s表示网络的源点,t表示网络的汇点. 对于每条边(u,v),有一个容量c(u,v) (c(u,v)=0) 如果c(u,v)=0，则表示(u,v)不存在于网络中。 如果原网络中不存在边(u,v)，则令c(u,v)=0 对于每条边(u,v),有一个流量f(u,v). 最大流问题 定义一个网络的流量（记为|f|）= 最大流问题，就是求在满足网络流性质的情况下，|f|的最大值。 弧的分类 若给定一个可行流F=(Fij),我们把网络中Fij=Cij的弧称作饱和弧， FijCij的弧称作非饱和弧， Fij=0的弧称作零流弧， Fij0的弧称作非零流弧 若P是网络中联结源点s和汇点t的的一条路(不用管边的有向性)，我们定义路的方向是从Vs到Vt，则路上的弧被分为两类：一类与路的方向一致，称为前向弧；另一类和路的方向相反，称为后向弧 残量网络 为了更方便算法的实现，一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。 r(u,v) = c(u,v) – f(u,v) 通俗地讲：就是对于某一条边（也称弧），还能再有多少流量经过。 Gf残量网络,Ef表示残量网络的边集. (a,b) 表示 (流量f,容量c) 从残量网络中可以清楚地看到： 因为存在边(s,v2) = 3,我们知道从S到v2还可以再增加3单位的流量； 因为存在边(v1,t) = 2,我们知道从v1到t还可以再增加2单位的流量。 为什么要建立后向弧 其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。 但是从v1到s不是和原网络中的弧的方向相反吗？显然“从v1到s还可以增加4单位流量”这条信息毫无意义。那么，有必要建立这些后向弧吗？ 为什么要建立后向弧 显然，例1中的画出来的不是一个最大流。 但是，如果我们把s - v2 - v1 - t这条路径经过的弧的流量都增加2,就得到了该网络的最大流。 注意到这条路径经过了一条后向弧:(v2,v1)。 如果不设立后向弧，算法就不能发现这条路径。 从本质上说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为（让2单位的流从v1流到v2) 可改进路（增广路） 可改进路定义：在残量网络中的一条从s通往t的路径，其中任意一条弧(u,v)，都有r[u,v]0。（每一条前向弧都是非饱和弧，每一条后向弧都是非零流弧） 绿色的即为一条可改进路。 可改进路算法 可改进路算法：每次用BFS找一条可改进路，然后沿着这条路径修改流量值（实际修改的是残量网络的边权），使得总流量变得更大，修正的方法是： 1、不属于可改进路P的弧一概不变 2、对于可改进路P上的所有前向弧加上a，后向弧减去a，这里a是一个可改进量。a既要尽量大，又要保证变化后0=Fij=Cij (满足容量限制和平衡条件) 。因此a=min(min(C前向弧ij－F前向弧ij),min(F