资源描述
会计学1第1页/共89页v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一个简单的一个简单的例子例子.网络可网络可以被想象成以被想象成一些输水的一些输水的管道管道.括号内括号内右边的数字右边的数字表示管道的表示管道的容量容量,左边的左边的数字表示这数字表示这条管道的当条管道的当前流量前流量.第2页/共89页1、容量限制容量限制: fu,v 0 )令令e(u) = f(V,u),称为称为u点的点的赢余，直观地描述，就是赢余，直观地描述，就是“流入的比流出的多多少流入的比流出的多多少”。e(v1)=4,e(v2)=3。不。不断将溢出的结点中的赢余断将溢出的结点中的赢余往后继点推进往后继点推进,直到赢余都直到赢余都聚集在聚集在t.第30页/共89页v1tsv2(2,2)(4,4)(0,4)(3,3)(2,2)如果多推了一些流量如果多推了一些流量, 我们可以再把它推回我们可以再把它推回来来. (如如e(v2)=3,但这但这3个单位的赢余已经没个单位的赢余已经没地方去了地方去了,只能推回来只能推回来.)(沿着后向弧沿着后向弧)这副图这副图是原网络而不是残量是原网络而不是残量网络网络,因此没把后项弧因此没把后项弧画出来画出来)第31页/共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个个单位怎么办单位怎么办?我们总不我们总不能尝试所有的可能性能尝试所有的可能性吧吧,那样就变成搜索了那样就变成搜索了.第32页/共89页推残量网络中的一条边.第33页/共89页第34页/共89页第35页/共89页第36页/共89页第37页/共89页正确性。后面我们将看到这个条件的作用.第38页/共89页第39页/共89页第40页/共89页第41页/共89页第42页/共89页第43页/共89页.1)对应重标号,2)对应推进,两者必能应用一个且只能应用一个.第44页/共89页第45页/共89页第46页/共89页第47页/共89页第48页/共89页第49页/共89页第50页/共89页fkkffEvvEvvEvv),(),(),(121101)()(1)()(1)()(12110kkvhvhvhvhvhvh相加得相加得:h(s)=h(t)+k=0+k=k而而k|V|,所以所以h(s)|V|.而根据定义而根据定义,h(s)=|V|.矛矛盾盾.第51页/共89页第52页/共89页第53页/共89页(一次性把某个结点所有的赢余全部推掉),复杂度降到了O(n3).第54页/共89页第55页/共89页第56页/共89页relabel操作只改变可行网络不改变残量网络,(w,u)不可能在relabel前存在于Ef而之后就不存在.第57页/共89页第58页/共89页第59页/共89页再一次检查的时候他们一定不是可行弧?第60页/共89页第61页/共89页第62页/共89页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第63页/共89页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第64页/共89页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第65页/共89页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第66页/共89页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第67页/共89页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第68页/共89页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第69页/共89页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页第71页/共89页.n推进操作不能创造可行弧,因此与列表的拓扑有序性无关.第72页/共89页第73页/共89页第74页/共89页第75页/共89页,的前面开始继续往下查找.第76页/共89页出的结点.因此该算法是正确的.第77页/共89页第78页/共89页第79页/共89页.,长得快一点.(在满足h函数的合法性和单调递增性的情况下)第80页/共89页过的算法仍然是正确的.第81页/共89页sv1v4v3t6543210v2v5第82页/共89页sv1v4v3t6543210v2v5第83页/共89页sv1v4v3t6543210v2v5第84页/共89页sv1v4v3t6543210v2v5第85页/共89页sv1v4v3t6543210v2v5第86页/共89页n备注中为我的Highest-relabel算法的代码(带BFS预处理和间隙优化) (150行)第87页/共89页nm未加优化未加优化加了两个优化加了两个优化50030000.600.06500300001.320.065001000001.430.06800100000Too long0.06（根本测（根本测不出来不出来）第88页/共89页
展开阅读全文