信息学奥赛 网络流算法介绍与分析优秀课件.ppt

信息学奥赛信息学奥赛 网络流算法介绍网络流算法介绍与分析与分析第1页，本讲稿共89页一些符号和定义一些符号和定义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).第2页，本讲稿共89页v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一个简单的一个简单的例子例子.网络可网络可以被想象成以被想象成一些输水的一些输水的管道管道.括号内括号内右边的数字右边的数字表示管道的表示管道的容量容量,左边的左边的数字表示这数字表示这条管道的当条管道的当前流量前流量.第3页，本讲稿共89页网络流的三个性质网络流的三个性质1、容量限制容量限制:fu,v v2-v1-t这条路径经过的弧这条路径经过的弧的流量都增加的流量都增加2,就得到了该网络的最大流。就得到了该网络的最大流。注意到这条路径经过了一条后向弧注意到这条路径经过了一条后向弧:(v2,v1)。如果不设立后向弧，算法就不能发现这条路径。如果不设立后向弧，算法就不能发现这条路径。从本质上说，后向弧为算法纠正自己所犯的错误从本质上说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行提供了可能性，它允许算法取消先前的错误的行为（让为（让2单位的流从单位的流从v1流到流到v2)第10页，本讲稿共89页为什么要建立后向弧为什么要建立后向弧当然当然,可以把上面说的情况当成特殊情况可以把上面说的情况当成特殊情况来处理。但使用后向弧可以使编程简单来处理。但使用后向弧可以使编程简单许多许多.注意注意,后向弧只是概念上的后向弧只是概念上的,在程序中后在程序中后向弧与前向弧并无区别向弧与前向弧并无区别.第11页，本讲稿共89页增广路增广路增广路定义：增广路定义：在残在残量网络中的一条从量网络中的一条从s通往通往t的路径，其的路径，其中任意一条弧中任意一条弧(u,v)，都有，都有ru,v0。绿色的即为一条增绿色的即为一条增广路。广路。v1tsv2232422第12页，本讲稿共89页增广路算法增广路算法增广路算法：每次用增广路算法：每次用BFS找一条最短找一条最短的增广路径，然后沿着这条路径修改的增广路径，然后沿着这条路径修改流量值（实际修改的是残量网络的边流量值（实际修改的是残量网络的边权）。当没有增广路时，算法停止，权）。当没有增广路时，算法停止，此时的流就是最大流。此时的流就是最大流。下面证明增广路算法的正确性下面证明增广路算法的正确性.第13页，本讲稿共89页将将f,c,r的定义域扩展为点集的定义域扩展为点集(在以后的叙述中在以后的叙述中,大写字母大写字母X,Y,S,T一般均表示一般均表示点集点集)点集间的流量和点集间的流量和:f(X,Y)=即即:X中的任意一点与中的任意一点与Y中的任意一点组成的所有中的任意一点组成的所有边上的流量之和边上的流量之和.(边的方向为从边的方向为从X中的结点到中的结点到Y中的结点中的结点)c,r等函数都有类似的定义等函数都有类似的定义.(点集间的容量和、点集间的容量和、点集间的残量网络容量和点集间的残量网络容量和)第14页，本讲稿共89页结论结论11.f(X,X)=0(由流量反对称性由流量反对称性)2.f(X,Y)=-f(Y,X)(有流量反对称性有流量反对称性)3.f(X Y,Z)=f(X,Z)+f(Y,Z)(显然显然)4.f(X,Y Z)=f(X,Y)+f(X,Z)(显然显然)第15页，本讲稿共89页最大流最小割定理最大流最小割定理网络流中这三个条件等价（网络流中这三个条件等价（在同一个时刻）:1、f是最大流是最大流2、残量网络中找不到增广路径、残量网络中找不到增广路径3、|f|=c(S,T)第16页，本讲稿共89页1、f是最大流是最大流2、残量网络中找不到增广路径、残量网络中找不到增广路径3、|f|=c(S,T)1-2证明证明:显然显然.假设有增广路径假设有增广路径,由于增广路径的容量至少为由于增广路径的容量至少为1,所以用所以用这个增广路径增广过后的流的流量肯这个增广路径增广过后的流的流量肯定要比定要比f的大的大,这与这与f是最大流矛盾是最大流矛盾.第17页，本讲稿共89页割的定义割的定义一个割一个割(S,T)由两个点集由两个点集S,T组成组成.S+T=Vs 属于属于 S.t 属于属于 T.提出割的定义提出割的定义,是为后面的证明作铺垫是为后面的证明作铺垫.第18页，本讲稿共89页结论结论2(点集总流量为零点集总流量为零)不包含不包含s和和t的点集的点集,于它相关联的边上的流量之于它相关联的边上的流量之和为和为0.证明证明:f(X,V)=(由流量平衡由流量平衡)=0 第19页，本讲稿共89页结论结论3任意割的流量等于整个网络的流量任意割的流量等于整个网络的流量.证明证明:f(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|的定义的定义)第20页，本讲稿共89页结论结论4网络的流量小于等于任意一个割的网络的流量小于等于任意一个割的容量容量.(注意注意这个与辅助定理这个与辅助定理3的区别的区别.这里是容量这里是容量)即即|f|=c(S,T)证明证明:|f|=f(S,T)=(由定义由定义)3证明证明:定义定义S=s v|在残量网络中在残量网络中s到到v有一条路径有一条路径;T=V-S.则则(S,T)是一个割是一个割.|f|=f(S,T)(由辅助定理由辅助定理3)而且而且,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)第22页，本讲稿共89页3-1证明证明:|f|0),那么那么|f|+d肯定不能满肯定不能满足上面的条件足上面的条件.1、f是最大流是最大流2、残量网络中找不到增广路径、残量网络中找不到增广路径3、|f|=c(S,T)第23页，本讲稿共89页增广路算法的正确性增广路算法的正确性如果如果 最大流最小割定理不能从最大流最小割定理不能从2推出推出3,那那么存在这样一种可能性么存在这样一种可能性:尽管找不到增广路径了尽管找不到增广路径了,但由于前面的错但由于前面的错误决策误决策,导致导致f还没有到达最大流还没有到达最大流,却不能却不能通过修改当前流来得到最大流通过修改当前流来得到最大流.但由于最大流最小割定理的三个条件互但由于最大流最小割定理的三个条件互相等价相等价(1-2,2-3,3-1),一个流是最大一个流是最大流流当且仅当它没有增广路径它没有增广路径.第24页，本讲稿共89页增广路算法的效率增广路算法的效率设设n=|V|,m=|E|每次增广都是一次每次增广都是一次BFS,效率为效率为O(m)所以所以,总共的时间复杂度为总共的时间复杂度为O(m*f*)其中其中f*为增广次数为增广次数.怎么求怎么求f*?第25页，本讲稿共89页f*对于随机数据对于随机数据,f*的值与的值与n比较接近比较接近.当当m不太大也不太小时不太大也不太小时,f*的值较大的值较大.(我出随机数据的方法是我出随机数据的方法是:固定地为源点固定地为源点和汇点连上一些边和汇点连上一些边,然后随机生成中间的然后随机生成中间的边边.中间的边保证边的两个端点的编号相中间的边保证边的两个端点的编号相差不太大差不太大.这与不少题目转成网络流后形这与不少题目转成网络流后形成的图相似成的图相似)第26页，本讲稿共89页f*的理论上界的理论上界考虑每一次增广考虑每一次增广,至少有一条边的至少有一条边的r(u,v)值等于增广路径的流量值等于增广路径的流量.称这些边为临界称这些边为临界边边.增广之后增广之后,这条临界边就在残量网络这条临界边就在残量网络中消失中消失.假设一条临界边对应一次增广假设一条临界边对应一次增广(事实上很事实上很难达到这样难达到这样),令每条边成为临界边的次令每条边成为临界边的次数为数为k(u,v),则有则有f*=O(m*k).k的上界的上界?第27页，本讲稿共89页k的上界的上界如果要让一条曾经的临界边如果要让一条曾经的临界边(u,v)再次成为临界边再次成为临界边,则则必须有一条增广路径包含边必须有一条增广路径包含边(v,u).因为每次增广之后因为每次增广之后临界边就消失临界边就消失,要让他再次成为临界边至少要让他再要让他再次成为临界边至少要让他再次在残量网络中出现次在残量网络中出现,即即(v,u)要被增广要被增广.结合上面的结论可以证明结合上面的结论可以证明,当算法取的增广路总是残当算法取的增广路总是残量网络中的最短路量网络中的最短路,任意一条边成为临界边的次数至任意一条边成为临界边的次数至多为多为n/2-1.因此因此,增广路算法的效率为增广路算法的效率为O(f*m)=O(km2)=O(nm2).(这只是个上界这只是个上界,一般情况是达不到的一般情况是达不到的)备注中为增广路算法我的代码实现。数组备注中为增广路算法我的代码实现。数组u是残量网络是残量网络的容量。的容量。第28页，本讲稿共89页预流推进算法预流推进算法下面将介绍一个更直观且时间效率下面将介绍一个更直观且时间效率更优的算法更优的算法.第29页，本讲稿共89页一个直观的想法一个直观的想法如果给你一个网络流如果给你一个网络流,让你手算出它的最让你手算出它的最大流大流,你会怎么算你会怎么算?一般人都会尝试着从源点出发一般人都会尝试着从源点出发,让每条边让每条边的流量尽可能得大的流量尽可能得大,然后一点点往汇点推然后一点点往汇点推,直到遇到一条比较窄的弧直到遇到一条比较窄的弧,原先的流量过原先的流量过不去了不去了,这才减少原先的流量这才减少原先的流量.第30页，本讲稿共89页v1tsv2(0,2)(4,4)(0,4)(3,3)(0,2)例例2.一个直观的想法一个直观的想法大致的思路：从源点出发，逐大致的思路：从源点出发，逐步推进。步推进。称当前状态下不满足流量平称当前状态下不满足流量平衡的结点为衡的结点为“溢出的结点溢出的结点”.(对于结点对于结点u,f(V,u)0)令令e(u)=f(V,u),称为称为u点的点的赢余，直观地描述，就是赢余，直观地描述，就是“流入的比流出的多多少流入的比流出的多多少”。e(v1)=4,e(v2)=3。不断将。不断将溢出的结点中的赢余往后继溢出的结点中的赢余往后继点推进点推进,直到赢余都聚集在直到赢余都聚集在t.第31页，本讲稿共89页v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)如果多推了一些流量如果多推了一些流量,我们可以再把它推回来我们可以再把它推回来.(如如e(v2)=3,但这但这3个个单位的赢余已经没地方单位的赢余已经没地方去了去了,只能推回来只能推回来.)(沿沿着后向弧着后向弧)这副图是原这副图是原网络而不是残量网络网络而不是残量网络,因此没把后项弧画出来因此没把后项弧画出来)例例2.一个直观的想法一个直观的想法第32页，本讲稿共89页v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)程序没有全局观程序没有全局观?!此时此时e(v2)=3.正确的回推正确的回推法是往法是往(v2,s)推推1,往往(v2,v1)推推2,然后使得这然后使得这2个单位的赢余可以从个单位的赢余可以从(v1,t)推到推到t上。上。但程序没有全局观但程序没有全局观,它万它万一往一往(v2,s)推了推了3个单位个单位怎么办怎么办?我们总不能尝试我们总不能尝试所有的可能性吧所有的可能性吧,那样就那样就变成搜索了变成搜索了.第33页，本讲稿共89页引导机制引导机制把流推错可能导致产生的流不是最大流把流推错可能导致产生的流不是最大流.我们需要有一个能引导流的推进方向的我们需要有一个能引导流的推进方向的机制机制,当它发现我们先前的推进是错误的当它发现我们先前的推进是错误的时候时候,能沿着正确的后向弧回推回来能沿着正确的后向弧回推回来.由于建立了后向弧由于建立了后向弧,正推与回推在程序中正推与回推在程序中并无却别，都是在推残量网络中的一条并无却别，都是在推残量网络中的一条边边.第34页，本讲稿共89页高度标号的引导作用高度标号的引导作用高度标号就是这样的一个引导机制高度标号就是这样的一个引导机制.我们规定我们规定,如果一个结点溢出了如果一个结点溢出了,那么他那么他的多余的流量只能流向高度标号比自己的多余的流量只能流向高度标号比自己低的结点低的结点.(“水往低处流水往低处流”)当然当然,高度标号不可能事先知道往哪些方高度标号不可能事先知道往哪些方向推才是正确的向推才是正确的.它将按情况动态改变自它将按情况动态改变自己的值己的值,从而正确地引导流向从而正确地引导流向.第35页，本讲稿共89页重标号操作重标号操作当一个结点有赢余当一个结点有赢余(溢出了溢出了),周围却没有周围却没有高度比它低的结点时候高度比它低的结点时候,我们就用重标号我们就用重标号操作使它的标号上升到比周围最低的结操作使它的标号上升到比周围最低的结点略高一点点略高一点,使他的赢余能流出去使他的赢余能流出去.赢余千万不能困在某个结点里赢余千万不能困在某个结点里.对于任意对于任意一个非源非汇的结点，有赢余就意味着一个非源非汇的结点，有赢余就意味着它不满足流量平衡，也就意味着整个网它不满足流量平衡，也就意味着整个网络流不是一个真正合法的网络流。络流不是一个真正合法的网络流。第36页，本讲稿共89页重标号操作重标号操作对于例对于例2的这种情况的这种情况,v2中过多的赢余最中过多的赢余最终会沿着终会沿着(v2,v1)、(v2,s)流回去流回去(虽然虽然他们一开始流错了方向他们一开始流错了方向,但后来又被回推但后来又被回推,等于说是被改正了等于说是被改正了)。只有当非源非汇的结点中的赢余全部流只有当非源非汇的结点中的赢余全部流到汇点或流回源点后，这个流才重新合到汇点或流回源点后，这个流才重新合法。法。第37页，本讲稿共89页高度函数高度函数高度函数高度函数h(v)返回一个返回一个v的高度标号。的高度标号。高度函数有三个基本条件：高度函数有三个基本条件：h(s)=|V|h(t)=0对于对于Ef(残量网络残量网络)中的每一条边中的每一条边(u,v),(r(u,v)0)h(u)0,那就表示从那就表示从u到到v还可以增加流量还可以增加流量,那那h(u)就应该比就应该比h(v)高才对高才对.的确的确,我们我们后面还将规定后面还将规定,只有在只有在h(u)h(v)的时候才能应用推进操作的时候才能应用推进操作(将一个结点的盈余推进到另一个结点的操作将一个结点的盈余推进到另一个结点的操作).而高度函数而高度函数为了满足其合法性为了满足其合法性,还要满足上述的这三个条件还要满足上述的这三个条件.后面我们后面我们将利用这三个条件证明预流推进算法的正确性。将利用这三个条件证明预流推进算法的正确性。第38页，本讲稿共89页高度函数的条件的实质高度函数的条件的实质h(u)0，r(u,v)0,h(u)=h(v)+1（u溢出，溢出，(u,v)在残量网络中，两者的在残量网络中，两者的高度差为高度差为1）推进量为推进量为e(u)与与r(u,v)的最小值。的最小值。推进时同时更改相关的推进时同时更改相关的r与与e的值。的值。第41页，本讲稿共89页推进操作推进操作 伪代码伪代码Procedure Push(u,v)lX min e(u),r(u,v)lDec(r(u,v),x)Inc(r(v,u),x)lDec(e(u),x)Inc(e(v),x)第42页，本讲稿共89页重标号操作重标号操作使用对象：使用对象：一个结点一个结点u使用条件：使用条件：结点结点u溢出；残量网络中周围所有的点的溢出；残量网络中周围所有的点的高度都不比它低。高度都不比它低。Relabel(u)lu(u)=min h(v)|(u,v)是残量网络总的边是残量网络总的边 +1使用了重标号操作后使用了重标号操作后,至少存在一个至少存在一个(u,v)满足满足h(u)=h(v)+1.第43页，本讲稿共89页预流初始化预流初始化(Init-Preflow)一开始的时候，我们要让和源点一开始的时候，我们要让和源点s相关连的边都尽相关连的边都尽可能的充满。但由于可能的充满。但由于s没有溢出，不符合推进操作没有溢出，不符合推进操作的使用条件，我们需要另写一段初始化的代码。的使用条件，我们需要另写一段初始化的代码。还得做的一件事是初始化高度函数还得做的一件事是初始化高度函数.h(s)=n h(v)=0 (vs)对于所有与对于所有与s相关联的点相关联的点v，lInc(e(v),c(s,v),Dec(e(s),c(s,v)l将边将边(s,v)反向，变成反向，变成(v,s)（在残量网络中）。（在残量网络中）。初始化过后，初始化过后，e(s)变成负数。变成负数。第44页，本讲稿共89页结论结论5对于一个对于一个溢出的结点溢出的结点，两个关键操作（推进，两个关键操作（推进和重标号）能且只能应用一个。和重标号）能且只能应用一个。证明：对于一个溢出的结点证明：对于一个溢出的结点u,和所有与他相和所有与他相关联的点关联的点v(u,v)在残量网络中存在在残量网络中存在),必然有必然有h(u)=h(v)+1.(由高度函数的定义由高度函数的定义).根据根据v分成两种情况分成两种情况:1).所有所有v都有都有h(u)h(v)+1 2).至少存在一个至少存在一个v,使得使得h(u)=h(v)+1.而而1)2)互为否命题互为否命题,不能同时成不能同时成立或同时不成立立或同时不成立.那么那么1)对应重标号对应重标号,2)对应对应推进推进,两者必能应用一个且只能应用一个两者必能应用一个且只能应用一个.第45页，本讲稿共89页一般的预流推进算法一般的预流推进算法由辅助定理由辅助定理5,得到了一个一般的预流推进得到了一个一般的预流推进算法算法.(好短好短)Init-PreflowWhile 存在一个溢出的结点存在一个溢出的结点l选一个结点选一个结点,应用相应的关键操作应用相应的关键操作(推进或重推进或重标号标号).当不存在溢出结点时当不存在溢出结点时(s,t不算不算),算法结算法结束束,得到一个可行流得到一个可行流,并且还是最大流并且还是最大流.第46页，本讲稿共89页预流推进算法的正确性预流推进算法的正确性预流只是不满足流量平衡预流只是不满足流量平衡,网络流的前两网络流的前两条性质条性质-容量限制和反对称性它还是满容量限制和反对称性它还是满足的足的.当不存在溢出结点时当不存在溢出结点时,流量平衡也流量平衡也满足了满足了.所以所以,当算法结束时当算法结束时,我们得到一个可行我们得到一个可行流流(合法流合法流).为什么他是一个最大流呢为什么他是一个最大流呢?下面先看几个结论下面先看几个结论:第47页，本讲稿共89页结论结论6(结点高度永不下降结点高度永不下降)只有重标号操作能更改结点的高度标号只有重标号操作能更改结点的高度标号.在重标号操作应用前在重标号操作应用前,必有必有h(u)=h(u)+1.所以所以,在重标号操作后在重标号操作后,高度标号至少高度标号至少+1.第48页，本讲稿共89页结论结论7在算法执行过程中在算法执行过程中,h始终是一个合法的始终是一个合法的高度函数高度函数.(满足那三个条件满足那三个条件)1).考察一个被重标号的结点考察一个被重标号的结点u.l设设(u,v)存在于存在于Ef,v0是所有是所有v中中h最小的一个最小的一个.H(u)=h(v0)+1,满足满足h(u)=h(v0)+1,而而h(v0)=h(v),所以所以 h(u)=h(v)+1.l设设(w,u)存在于存在于Ef,则则h(w)=h(u)+1=h(u)+1.仍旧满足仍旧满足.第49页，本讲稿共89页结论结论7在算法执行过程中在算法执行过程中,h始终是一个合法的始终是一个合法的高度函数高度函数.(满足那三个条件满足那三个条件)2).考察一个被推进的边考察一个被推进的边(u,v).l(v,u)可能是在这次推进之后才出现在可能是在这次推进之后才出现在Ef中中.它的出现使得新增了一个限制条件它的出现使得新增了一个限制条件:h(v)=h(u)+1.不过不过,这显然是满足的这显然是满足的,因为因为推进操作的使用条件是推进操作的使用条件是h(u)=h(v)+1.那么那么h(v)=h(u)-1=h(u)+1第50页，本讲稿共89页结论结论8(预流中无增广路预流中无增广路)当当h是一个合法的高度函数时是一个合法的高度函数时,Gf中始终不中始终不存在增广路存在增广路.(这个定理展示了这个定理展示了h的条件的的条件的重要性和巧妙性重要性和巧妙性)证明证明:假设存在增广路假设存在增广路p=(v0,v1,vk),其其中中v0=s,vk=t.因为增广路径中无重复点因为增广路径中无重复点,k+1=|V|,即即k|V|.第51页，本讲稿共89页结论结论8(预流中无增广路预流中无增广路)相加得相加得:h(s)=h(t)+k=0+k=k而而k|V|,所以所以h(s)|V|.而根据定义而根据定义,h(s)=|V|.矛盾矛盾.第52页，本讲稿共89页预流推进算法的正确性预流推进算法的正确性当有溢出结点时当有溢出结点时,根据结论根据结论5,必定可以在它上面施加必定可以在它上面施加一个操作一个操作.当算法停止时当算法停止时,因为无溢出结点因为无溢出结点,所以当前流是一个所以当前流是一个合法流合法流,而根据结论而根据结论8,Gf中始终不存在增广路中始终不存在增广路.根据根据最大流最小割定理最大流最小割定理,当当Gf中不存在增广路时中不存在增广路时,当前流当前流是最大流是最大流.(算法执行了一半时虽然也没有增广路算法执行了一半时虽然也没有增广路,但由于它但由于它不是一个合法流不是一个合法流,前面的诸多定理都不成立前面的诸多定理都不成立).算法的最优性的保证者算法的最优性的保证者:对于所有在对于所有在Ef中的中的(v,u),均有均有h(v)0lh(u)=h(v)+1可行边集可行边集Ef,h:所有由可行弧组成的集合。所有由可行弧组成的集合。可行网络可行网络Gf,h=(V,Ef,h)第56页，本讲稿共89页结论结论9,10结论结论9:可行网络中无环可行网络中无环.(和结论和结论8的证明的证明类似类似,弄一堆式子然后叠加一下弄一堆式子然后叠加一下,导出矛导出矛盾盾)结论结论10:推进操作永远不会新增可行弧推进操作永远不会新增可行弧,却可能使原有的可行弧消失却可能使原有的可行弧消失.(根据可行根据可行弧的定义显然弧的定义显然)第57页，本讲稿共89页结论结论11在在u被重标号之后被重标号之后:l1).至少有一条可行弧离开至少有一条可行弧离开u.显然显然.设设v0是是u的邻居中的邻居中h值最小的那一个值最小的那一个,则则(u,v0)必定是一条可行弧必定是一条可行弧.l2).不可能有可行弧进入不可能有可行弧进入u.假设有一条假设有一条(w,u).则则h(w)=h(u)+1.根据根据辅助定理辅助定理6,relabel操作至少将结点的操作至少将结点的h+1,所所以以h(w)h(u)+1.根据高度函数必须满足的根据高度函数必须满足的条件条件,(w,u)在在relabel前不在前不在Ef中中.而而relabel操作只改变可行网络不改变残量网络操作只改变可行网络不改变残量网络,(w,u)不可能在不可能在relabel前存在于前存在于Ef而之后就不存在而之后就不存在.第58页，本讲稿共89页当前弧当前弧每个结点有一个邻居列表和有一个每个结点有一个邻居列表和有一个“当前弧当前弧”的指针的指针,保存当前检查到邻居列表中的哪一条弧了。初始化保存当前检查到邻居列表中的哪一条弧了。初始化时时,“当前弧当前弧”指向与该结点相连的第一条边指向与该结点相连的第一条边.邻居邻居列表保存的是所有可能成为可行弧的弧列表保存的是所有可能成为可行弧的弧.当再次调用检查操作时当再次调用检查操作时,可以从上一次检查了一半的可以从上一次检查了一半的地方继续检查地方继续检查.具体请看下面检查操作的伪代码具体请看下面检查操作的伪代码:第59页，本讲稿共89页检查操作检查操作Check(u)lWhile e(u)0 dolIf current(u)degree(u)then/当没有可行弧可以推当没有可行弧可以推进进,该结点却仍旧有赢余时该结点却仍旧有赢余时,重标号重标号.lRelabel(u)lCurrent(u)=1lElselIf (u,current(u)是一条可行弧是一条可行弧 then Push(u,current(u)/push了之后就不能增加了之后就不能增加 current(u)的值的值.因为这因为这如果是一次非饱和推进如果是一次非饱和推进,那再下一次检查时还是可以沿那再下一次检查时还是可以沿着这条弧做推进着这条弧做推进.lElse Inc(current(u)第60页，本讲稿共89页当前弧的正确性当前弧的正确性Current是全局变量是全局变量,当某次当某次Check操作操作结束时他的值并没有被清空结束时他的值并没有被清空.比如结点比如结点u有有10个邻居个邻居,上次检查到第上次检查到第7个个,那再一次那再一次Check(u)的时候就只要从第的时候就只要从第7个个开始检查就可以了。开始检查就可以了。为什么再一次检查的时候不要检查第为什么再一次检查的时候不要检查第1-6条边了条边了?能否证明在再一次检查的时候他能否证明在再一次检查的时候他们一定不是可行弧们一定不是可行弧?第61页，本讲稿共89页当前弧的正确性当前弧的正确性在在relabel-to-front算法中算法中,relabel只被只被Check调用调用.当当“当前弧当前弧”移动时移动时,移动前它指向的那移动前它指向的那条弧一定是不可行的条弧一定是不可行的.而推进操作不能创而推进操作不能创造可行弧造可行弧.只有只有relabel可以可以.两次两次Check之间没有之间没有relabel操作操作.所以原先的不可行所以原先的不可行的弧在第二次的弧在第二次Check之前一直是不可行之前一直是不可行的的.第62页，本讲稿共89页Relabel-to-frontInit-Preflow初始化结点初始化结点(除除s,t)列表列表L(任何顺序均可任何顺序均可)令所有令所有u,Current(u)=1u HeadLWhile u nil dolOld-height h(u)lCheck(u)lIf h(u)old-height then 将将u移到移到L首部首部l/如果如果h(u)比原先的比原先的h高了高了,说明被说明被relabel,移到队首移到队首.lu next(u)第63页，本讲稿共89页图例图例(初始状态初始状态.结点下方数字为赢余结点下方数字为赢余,N显示的是邻居列显示的是邻居列表表,N中红色的是当前弧指针所在的位置中红色的是当前弧指针所在的位置.)S-26x12y14z0t06543210(12/12)(14/14)(0/16)(0/7)(0,5)(0,8)(0,10)L x y zN s s xy x yz z tt第64页，本讲稿共89页图例图例:x被检查并重标号被检查并重标号,并被提到并被提到L的首部的首部(等于没提等于没提).注注意当前弧的指针移到了意当前弧的指针移到了t.x的所有赢余推给了的所有赢余推给了y和和t.S-26x0y19z0t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(0,8)(0,10)L x y zN s s xy x yz z tt第65页，本讲稿共89页图例图例:y正在被检查正在被检查.将将8单位的赢余推给单位的赢余推给z之后还是有之后还是有剩余剩余.S-26x0y11z8t76543210(12/12)(14/14)(7/16)(0/7)(5,5)(8,8)(0,10)L x y zN s s xy x yz z tt第66页，本讲稿共89页图例图例:一次必须把赢余全部推光一次必须把赢余全部推光.所以所以y被重标号被重标号,当前弧指针从头当前弧指针从头开始查找开始查找,找到找到(y,x)这条可行弧之后进行推进这条可行弧之后进行推进.实际上是把多推实际上是把多推的赢余还给了的赢余还给了x.因为因为h(u)=h(v)+1的保证的保证,它没有把赢余错推给它没有把赢余错推给s.S-26x5y6z8t76543210(12/12)(14/14)(7/16)(0/7)(0,5)(8,8)(0,10)L x y zN s s xy x yz z tt第67页，本讲稿共89页图例图例:y还是有赢余还是有赢余.当当前弧移动到另局列表的尾部时当当前弧移动到另局列表的尾部时,y再一再一次被重标号次被重标号,并把赢余还给并把赢余还给s.检查结束检查结束,y被提到被提到L列表的首部列表的首部.S-20 x5y0z8t76543210(12/12)(8/14)(7/16)(0/7)(0,5)(8,8)(0,10)L y x zN s s xx y yz z tt第68页，本讲稿共89页图例图例:检查检查x.注意注意x的当前弧指针已经指在的当前弧指针已经指在t上了上了.x把把赢余推给赢余推给t.u指针直接后移指针直接后移.(因为因为x没有被重标号没有被重标号)S-20 x0y0z8t126543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(0,10)L y x zN s s xx y yz z tt第69页，本讲稿共89页图例图例:z被检查并被提到列表首部被检查并被提到列表首部.S-20 x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)L z y xN x s sy x ytz zt第70页，本讲稿共89页图例图例:u指针从指针从y开始向后移动开始向后移动,直到队尾也没有发现可以直到队尾也没有发现可以检查的结点检查的结点(只有溢出的结点才能被检查只有溢出的结点才能被检查).算法结束算法结束.S-20 x0y0z0t206543210(12/12)(8/14)(12/16)(0/7)(0,5)(8,8)(8,10)L z y xN x s sy x ytz zt第71页，本讲稿共89页relabel-to-front的正确性的正确性前面我们已经证明了一般预流推进算法前面我们已经证明了一般预流推进算法的正确性了的正确性了.因此因此,现在只要证明现在只要证明,在在relabel-to-front算法结束时算法结束时,一般预流推一般预流推进算法的结束条件也正好被满足进算法的结束条件也正好被满足-即即没有溢出的结点没有溢出的结点.第72页，本讲稿共89页结论结论11:L始终拓扑有序始终拓扑有序对于对于G上的可行网络上的可行网络Gf,h,列表列表L中的结点中的结点始终保持拓扑有序性始终保持拓扑有序性.一开始的时候一开始的时候,列表中所有结点列表中所有结点(s,t不在不在列表中列表中)的高度均为的高度均为0,不存在高度差不存在高度差,所以所以不存在可行弧不存在可行弧.这时列表显然拓扑有序这时列表显然拓扑有序.一个结点被一个结点被relabel之后之后,就被提到列表的就被提到列表的首部首部.根据辅助定理根据辅助定理11,relabel之后没有之后没有可行弧进入结点可行弧进入结点,但有可行弧离开结点但有可行弧离开结点,所以将结点提到列表首部仍旧使列表满所以将结点提到列表首部仍旧使列表满足拓扑有序足拓扑有序.推进操作不能创造可行弧推进操作不能创造可行弧,因此与列表的因此与列表的拓扑有序性无关拓扑有序性无关.第73页，本讲稿共89页结论结论12L中指针中指针u之前的结点全部是非溢出结点之前的结点全部是非溢出结点.当一个结点被检查之后当一个结点被检查之后,它必定没有赢余它必定没有赢余,因此将因此将u指指针后移不影响上面的性质针后移不影响上面的性质.它自己没有赢余了它自己没有赢余了,但它却可能将赢余推给了别人但它却可能将赢余推给了别人.如果推给在如果推给在L中位置在它后面的结点不要紧中位置在它后面的结点不要紧.但如果但如果它把赢余推给了在自己之前的结点呢它把赢余推给了在自己之前的结点呢?因为因为L拓扑有序拓扑有序,他若把赢余推给了排在自己前面的他若把赢余推给了排在自己前面的结点结点,则必定发生了则必定发生了relabel操作操作.而如果有而如果有relabel,则则它已经被提到列表的首部了它已经被提到列表的首部了.性质依然满足性质依然满足.这就是算法名这就是算法名:relabel-to-front的由来的由来.第74页，本讲稿共89页Relabel-to-front根据一般的预流推进算法根据一般的预流推进算法,当没有溢出结当没有溢出结点时算法就结束并得到一个最大流点时算法就结束并得到一个最大流.而而relabel-to-front算法的结束条件是算法的结束条件是u指指针指向针指向L队列尾部队列尾部.根据辅助定理根据辅助定理12,u以前的结点均非溢出以前的结点均非溢出结点结点.所以当所以当u指向尾部时指向尾部时,所有的结点均所有的结点均没有溢出没有溢出.另外可以证明另外可以证明,算法的复杂度为算法的复杂度为O(n3).第75页，本讲稿共89页Highest-relabel还可以改进还可以改进.经验表明经验表明,总是检查高度标号最大的结点，总是检查高度标号最大的结点，会有比较好的效率会有比较好的效率.于是对于是对Relabel-to-front进行了一点小修进行了一点小修改改,得到了得到了highest-relabel算法算法.第76页，本讲稿共89页分块的分块的L列表列表可以证明可以证明,任意结点的最大的距离标号为任意结点的最大的距离标号为2n-1.将将L列表分成列表分成2n个块个块,第第1块保存所有高度块保存所有高度为为0的点的点,第第i+1块保存高度为块保存高度为I的所有结点的所有结点.从最后一块开始往前找从最后一块开始往前找,发现一个不为空发现一个不为空的块就把这个块里的结点全部检查掉的块就把这个块里的结点全部检查掉.如如果有元素被重标号了果有元素被重标号了,那就将他移动到新那就将他移动到新的块里的块里,并从那个新的块的前面开始继续并从那个新的块的前面开始继续往下查找往下查找.第77页，本讲稿共89页分块的分块的L列表列表对于可行网络对于可行网络,分块分块L列表是拓扑有序的列表是拓扑有序的.因为可行弧因为可行弧(u,v)要求要求h(u)=h(v)+1,即即只有从标号高的结点指向标号低的结点只有从标号高的结点指向标号低的结点.既只有从后面的块里的结点指向前面的既只有从后面的块里的结点指向前面的块里的结点块里的结点.所以所以,这种分块方法仍然保这种分块方法仍然保持了整个列表的拓扑有序性持了整个列表的拓扑有序性.因此因此,算法算法结束时没有溢出的结点结束时没有溢出的结点.因此该算法是正因此该算法是正确的确的.第78页，本讲稿共89页分块分块L列表的实现列表的实现如果用链表，可以只占用如果用链表，可以只占用O(n)的空间。的空间。在内存不紧张的情况下，也完全可以用在内存不紧张的情况下，也完全可以用无序数组，时间效率不比链表差无序数组，时间效率不比链表差,虽然空虽然空间是间是O(n2)的的.无序数组在删除的时候，可以用无序数组在删除的时候，可以用:Delete(i)l