西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 网络流网络流计算机学院计算机学院西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 网络流问题网络流问题由于人类对自然资源的消耗，人们意识到大约在由于人类对自然资源的消耗，人们意识到大约在2300年年之后，地球就不能再居住了。于是在月球上建立了新的绿之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，地，以便在需要时移民。令人意想不到的是，2177年冬年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有最短的时间内迁往月球。现有n个太空站位于地球与月球个太空站位于地球与月球之间，且有之间，且有m艘公共交通太空船在其间来回穿梭。每个太艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船空站可容纳无限多的人，而每艘太空船i只可容纳只可容纳Hi个个人。每艘太空船将周期性地停靠一系列的太空站，例如：人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4)表示该太空船将周期性地停靠太空站表示该太空船将周期性地停靠太空站134134134。每一艘太空船从一个太空站驶往任一太。每一艘太空船从一个太空站驶往任一太空站耗时均为空站耗时均为1。人们只能在太空船停靠太空站。人们只能在太空船停靠太空站(或月球、或月球、地球地球)时上、下船。初始时所有人全在地球上，太空船全时上、下船。初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。移到月球上的运输方案。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 网络流问题网络流问题由文件由文件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=0)n如果c(u,v)=0，则表示(u,v)不存在于网络中。n如果原网络中不存在边(u,v)，则令c(u,v)=0n对于每条边(u,v),有一个流量f(u,v).西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 网络流的三个性质网络流的三个性质1、容量限制容量限制: fu,v=cu,v2、反对称性反对称性：fu,v = - fv,u3、流量平衡流量平衡: 对于不是源点也不是汇点的对于不是源点也不是汇点的任意结点任意结点,流入该结点的流量和等于流出该流入该结点的流量和等于流出该结点的流量和。结点的流量和。结合反对称性结合反对称性,流量平衡也可以写成流量平衡也可以写成:只要满足这三个性质只要满足这三个性质,就是一个合法的网络就是一个合法的网络流流,也称为也称为可行流可行流。可行流至少有一个零流。可行流至少有一个零流。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最大流问题n定义一个网络的流量（记为定义一个网络的流量（记为|f|）=n最大流最大流问题，就是求在满足网络流性质的情况下，问题，就是求在满足网络流性质的情况下，|f|的最大值。的最大值。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 弧的分类弧的分类n若给定一个可行流若给定一个可行流F=(Fij),我们把网络中我们把网络中Fij=Cij的弧称作饱和弧，的弧称作饱和弧，Fij0的弧称作非零流弧的弧称作非零流弧n若若P是网络中联结源点是网络中联结源点s和汇点和汇点t的的一条路的的一条路(不用不用管边的有向性管边的有向性)，我们定义路的方向是从，我们定义路的方向是从Vs到到Vt，则路上的弧被分为两类：一类与路的方向一致，则路上的弧被分为两类：一类与路的方向一致，称为前向弧；另一类和路的方向相反，称为后向称为前向弧；另一类和路的方向相反，称为后向弧弧西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 残量网络残量网络n为了更方便算法的实现，一般根据原网络定义一为了更方便算法的实现，一般根据原网络定义一个残量网络。其中个残量网络。其中r(u,v)为残量网络的容量。为残量网络的容量。nr(u,v)=c(u,v)f(u,v)n通俗地讲：就是对于某一条边（也称弧），还能通俗地讲：就是对于某一条边（也称弧），还能再有多少流量经过。再有多少流量经过。nGf残量网络残量网络,Ef表示残量网络的边集表示残量网络的边集.西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China (a,b)表示表示(流量流量f,容量容量c)v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422如果网络中一条边的容量为如果网络中一条边的容量为0,则认为这条边不在残量网络中。则认为这条边不在残量网络中。r(s,v1)=0,所以就不画出来了。另外举个例子：所以就不画出来了。另外举个例子：r(v1,s) = c(v1,s) f(v1,s) = 0 (-f(s,v1) = f(s,v1) = 4.图1 原网络图2 残量网络西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China n从从残量网络中可以清残量网络中可以清楚地看到：楚地看到：n因为存在边因为存在边(s,v2)=3,我们知道从我们知道从S到到v2还可以再增加还可以再增加3单位的单位的流量；流量；n因为存在边因为存在边(v1,t)=2,我们知道从我们知道从v1到到t还还可以再增加可以再增加2单位的流单位的流量。量。v1tsv2232422西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 为什么要建立后向弧为什么要建立后向弧n其中像其中像(v1,s)这样的边这样的边称为后向弧称为后向弧,它表示从它表示从v1到到s还可以增加还可以增加4单位单位的流量。的流量。n但是从但是从v1到到s不是和原不是和原网络中的弧的方向相反网络中的弧的方向相反吗？显然吗？显然“从从v1到到s还还可以增加可以增加4单位流量单位流量”这条信息毫无意义。那这条信息毫无意义。那么，有必要建立这些后么，有必要建立这些后向弧吗？向弧吗？v1tsv2232422西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 为什么要建立后向弧为什么要建立后向弧n显然，例显然，例1中的画出来的不是一个最大流。中的画出来的不是一个最大流。n但是，如果我们把但是，如果我们把s-v2-v1-t这条路径经过的弧这条路径经过的弧的流量都增加的流量都增加2,就得到了该网络的最大流。就得到了该网络的最大流。n注意到这条路径经过了一条后向弧注意到这条路径经过了一条后向弧:(v2,v1)。n如果不设立后向弧，算法就不能发现这条路径。如果不设立后向弧，算法就不能发现这条路径。n从本质上说，后向弧为算法纠正自己所犯的错误提供了可从本质上说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为（让能性，它允许算法取消先前的错误的行为（让2单位的流单位的流从从v1流到流到v2)西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 可改进路（增广路）可改进路（增广路）n可改进路定义：可改进路定义：在残在残量网络中的一条从量网络中的一条从s通通往往t的路径，其中任意的路径，其中任意一条弧一条弧(u,v)，都有都有ru,v0。（每一条（每一条前向弧都是非饱和弧，前向弧都是非饱和弧，每一条后向弧都是非每一条后向弧都是非零流弧）零流弧）n绿色的即为一条可改绿色的即为一条可改进路。进路。v1tsv2232422西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 可改进路算法可改进路算法n可改进路算法：每次用可改进路算法：每次用BFS找一条可改进路，然找一条可改进路，然后沿着这条路径修改流量值（实际修改的是残量后沿着这条路径修改流量值（实际修改的是残量网络的边权），使得总流量变得更大，修正的方网络的边权），使得总流量变得更大，修正的方法是：法是：1、不属于可改进路、不属于可改进路P的弧一概不变的弧一概不变2、对于可改进路、对于可改进路P上的所有前向弧加上上的所有前向弧加上a，后向后向弧减去弧减去a，这里，这里a是一个可改进量。是一个可改进量。a既要尽量大，既要尽量大，又要保证变化后又要保证变化后0=Fij2证明证明:显然显然.假设有增广路径假设有增广路径,由于由于增广路径的容量至少为增广路径的容量至少为1,所以用这个增广路所以用这个增广路径增广过后的流的流量肯定要比径增广过后的流的流量肯定要比f的大的大,这与这与f是是最大流矛盾最大流矛盾.西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 结论结论2(点集总流量为零点集总流量为零)n不包含不包含s和和t的点集的点集,与它相关联的边上的流量之和为与它相关联的边上的流量之和为0.n证明证明:f(X,V)=(由流量平衡由流量平衡)=0西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 结论结论3n任意割的流量等于整个网络的流量任意割的流量等于整个网络的流量.n证明证明:nf(S,T)=f(S,V)f(S,S)(由辅助定理由辅助定理1) = f(S,V) (由辅助定理1) = f(S,V) + f(S s,V) (同上) = f(s,V) (由辅助定理2) = |f| (由|f|的定义)西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 结论结论4n网络的流量小于等于任意一个割的网络的流量小于等于任意一个割的容量容量.(注意这个与辅助注意这个与辅助定理定理3的区别的区别.这里是容量这里是容量)n即即|f|=c(S,T)n证明证明:|f|=f(S,T)=(由定义由定义)3证明证明:定义定义S=sv|在残量网络中在残量网络中s到到v有一有一条路径条路径;T=V-S.则则(S,T)是一个割是一个割.n|f|=f(S,T)(由辅助定理由辅助定理3)n而且而且,r(S,T)=0.假设不为假设不为0,则在残量网络中则在残量网络中,两个集两个集合间必定有边相连合间必定有边相连,设在设在S的一端的一端为为v,在在T的一端为的一端为u.那么那么,s就可以通过就可以通过v到达到达u,那么根据那么根据S的定义的定义,u就应该在就应该在S中中.矛盾矛盾.所以所以,|f|=f(S,T)=c(S,T)r(S,T)=c(S,T)1、f是最大流是最大流2、残量网络中找不到增广路径、残量网络中找不到增广路径3、|f|=c(S,T)西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China n3-1证明证明:|f|0),那么那么|f|+d肯定不能满足上面肯定不能满足上面的条件的条件.1、f是最大流是最大流2、残量网络中找不到增广路径、残量网络中找不到增广路径3、|f|=c(S,T)西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 标号法寻求可改进路（标号法寻求可改进路（Ford-Fulkerson算法）算法）从一个可行流从一个可行流F出发（可以设为零流），经过标号过程和调整过程。出发（可以设为零流），经过标号过程和调整过程。标号过程标号过程:网络中的顶点或者是标号点网络中的顶点或者是标号点(分为已检查和未检查两种分为已检查和未检查两种)，或者是未标，或者是未标号点，每个标号点分为两部分号点，每个标号点分为两部分(标号从哪个顶点得到，确定可改进量标号从哪个顶点得到，确定可改进量a)。标号过程开始，总先给标号过程开始，总先给Vs标上标上(0,+)，这时是标号而未检查的顶，这时是标号而未检查的顶点，其余都是未标号点。取一个标号而未检查的标号点，其余都是未标号点。取一个标号而未检查的标号Vi，对一切未标号点，对一切未标号点Vj：在在Vi的全部相邻顶点都已标号后，的全部相邻顶点都已标号后，Vi成为标号而已检查过的顶点。重成为标号而已检查过的顶点。重复上述步骤，一旦复上述步骤，一旦Vt被标上号，表明得到一条从被标上号，表明得到一条从Vs到到Vt的可改进路的可改进路P，转入调整过程。转入调整过程。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 标号法寻求可改进路（标号法寻求可改进路（Ford-Fulkerson算法）算法）调整过程：调整过程：采用采用“倒向追踪倒向追踪”的方法，从的方法，从Vt开始，利用第一个标号找出可改进路开始，利用第一个标号找出可改进路P，并，并以以Vt的第二个标号的第二个标号L(Vt)作为改进量作为改进量a，改进，改进P上的流量。上的流量。例如：设例如：设Vt的第一个标号为的第一个标号为Vk(或或-Vk)，则弧，则弧(Vk,Vt)(或或(Vt,Vk)是是P上的上的弧，接下来再检查弧，接下来再检查Vk的第一个标号，如此继续下去的第一个标号，如此继续下去.，直到查倒，直到查倒Vs为止。为止。这时被找出的弧构成了这时被找出的弧构成了P。令改进量令改进量a=L(Vt)，即，即Vt的第二个标号。的第二个标号。去掉所有的标号，对新的可行流去掉所有的标号，对新的可行流Fij，重新进入标号过程。直到标号过程无重新进入标号过程。直到标号过程无法继续。法继续。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 例例1求如下网络的最大流求如下网络的最大流V2VtVsV1V4V3(3,3)(1,5)(3,4)(3,5)(1,1)(1,1)(2,2)(1,2)(0,3)西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 标号法分析例标号法分析例11.标号过程标号过程(1)首先给首先给Vs标上标上(0,+)(2)检查检查Vs。弧。弧(Vs,V2)上，上，Fs2=Cs2=3，不满足，不满足标号条件；弧标号条件；弧(Vs,V1)上，上，Fs1=10，则给，则给V2记下标号为记下标号为(-V1,L(V2)，其中，其中L(V2)minL(V1),F21=min4,1=1西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 标号法分析例标号法分析例1(4)检查检查V2。弧。弧(V2,V4)上，上，F24=3C24=4，则，则给给V4标号标号(V2,L(V4)，其中，其中L(V4)=minL(V2),C24-F24=min1,1=1同理，标注同理，标注V3为为(-V2,1).(5)在在V3，V4中任选一个进行检查，如中任选一个进行检查，如V4。弧。弧(V4,Vt)上，上，F4t=30时有上下界的网络不一定时有上下界的网络不一定存在可行流了。存在可行流了。那么如何判断一个有上下界的网络有无可行流呢那么如何判断一个有上下界的网络有无可行流呢？西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 容量有上下界的网络的最大流容量有上下界的网络的最大流算法思路：将原网络转换为一个附加网络。算法思路：将原网络转换为一个附加网络。1.新增加两个顶点新增加两个顶点和和，分别称为附加源和附加汇，分别称为附加源和附加汇2.对原网络对原网络N的每个顶点的每个顶点U加一条新弧加一条新弧，这条弧的容量为以，这条弧的容量为以U为尾的弧的容量下限之和。为尾的弧的容量下限之和。3.对原网络对原网络N的每个顶点的每个顶点U加一条新弧加一条新弧，这条弧的容量为以，这条弧的容量为以U为头的弧的容量下限之和。为头的弧的容量下限之和。4.原网络的弧仍保留，弧容量修正为原网络的弧仍保留，弧容量修正为C(e)-B(e)5.再添两条新弧再添两条新弧e=st,e=ts。其容量均为。其容量均为6.用标号法求此新网络的最大流，若结果能使流出用标号法求此新网络的最大流，若结果能使流出的的一切弧都满载，则原网络有可行流一切弧都满载，则原网络有可行流F(e)F(e)B(e)，否则无可行流。，否则无可行流。7.在原网络中运用标号法将可行流放大，从而得出最大流。在原网络中运用标号法将可行流放大，从而得出最大流。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 容量有上下界的网络的最大流容量有上下界的网络的最大流例原网络，第一个数字为例原网络，第一个数字为B(e)，第二个为，第二个为C(e)西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 容量有上下界的网络的最大流容量有上下界的网络的最大流按照上述算法求得按照上述算法求得附加网络，并用标附加网络，并用标号法求此网络的最号法求此网络的最大流。大流。发现从发现从流出的流流出的流都满载，所以有可都满载，所以有可行流。行流。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 容量有上下界的网络的最大流容量有上下界的网络的最大流按照按照F(e)F(e)B(e)将此最大流还原为原将此最大流还原为原网络的最大流网络的最大流西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 容量有上下界的网络的最大流容量有上下界的网络的最大流用标号法进行可行流放大，得到最大流用标号法进行可行流放大，得到最大流10西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 容量有上下界的网络的最小流容量有上下界的网络的最小流n按照前述附加网络方法求得可行流，只不过在放按照前述附加网络方法求得可行流，只不过在放大可行流时，以大可行流时，以t为源点，为源点，s为汇点进行，倒向求为汇点进行，倒向求出的最大流为从出的最大流为从s到到t到的最小流。到的最小流。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题最小费用最大流问题n求运输量最大且费用最少求运输量最大且费用最少的运输方案的运输方案n求一个最大流，使得此式求一个最大流，使得此式取最小值取最小值西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题最小费用最大流问题算法思想：算法思想：若若F是所有可行流中费用最小的，而是所有可行流中费用最小的，而P是关于是关于F的的所有可改进路中费用最小的，沿着所有可改进路中费用最小的，沿着P取调整取调整F最大，最大，则得到的流为最小费用最大流。则得到的流为最小费用最大流。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题最小费用最大流问题步骤：步骤：1.取取F(0)=0;2.若第若第k-1步得到最小费用流步得到最小费用流F(k-1)，则构造赋权有向图，则构造赋权有向图W(F(k-1)，在，在W(F(k-1)中，寻求从中，寻求从Vs到到Vt的最短路径。的最短路径。若不存在最短路若不存在最短路(即最短路为即最短路为+)，则，则F(k-1)为最小费用最为最小费用最大流；若存在最短路，则为可改进路大流；若存在最短路，则为可改进路P，在，在P上对上对F(k-1)进行进行调整。调整。3.其中，赋权有向图其中，赋权有向图W(F(k)的构造规则为：其顶点是原网络的构造规则为：其顶点是原网络的顶点，而每条弧变为两个方向相反的弧，定义权值的顶点，而每条弧变为两个方向相反的弧，定义权值Wij为为西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题最小费用最大流问题4.在在P上对上对F(k-1)进行调整的方法为：进行调整的方法为：5.得到新流得到新流F(k)，再对，再对F(k)重复上述步骤，直到重复上述步骤，直到不存在最短路径。不存在最短路径。西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题例最小费用最大流问题例西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题例最小费用最大流问题例西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题例最小费用最大流问题例西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题例最小费用最大流问题例西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 最小费用最大流问题例最小费用最大流问题例西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 作业作业n本课算法的实现本课算法的实现n标号法标号法n容量有上下界网络的最大流容量有上下界网络的最大流n容量有上下界网络的最小流容量有上下界网络的最小流n最小费用最大流最小费用最大流