網(wǎng)絡(luò)流算法完整版本

網(wǎng)絡(luò)流算法專題

引例：運(yùn)輸網(wǎng)絡(luò)現(xiàn)在想將一些物資從S運(yùn)抵T，必須經(jīng)過一些中轉(zhuǎn)站。連接中轉(zhuǎn)站的是公路，每條公路都有最大運(yùn)載量。每條弧代表一條公路，弧上的數(shù)表示該公路的最大運(yùn)載量。最多能將多少貨物從S運(yùn)抵T？4248473621STV1V2V3V4公路運(yùn)輸圖最大流基本概念這是一個典型的網(wǎng)絡(luò)流模型。為了解答此題，我們先了解網(wǎng)絡(luò)流的有關(guān)定義和概念。若有向圖G=(V,E)滿足下列條件：有且僅有一個頂點(diǎn)S，它的入度為零，即d-(S)=0，這個頂點(diǎn)S便稱為源點(diǎn)，或稱為發(fā)點(diǎn)。有且僅有一個頂點(diǎn)T，它的出度為零，即d+(T)=0，這個頂點(diǎn)T便稱為匯點(diǎn)，或稱為收點(diǎn)。每一條弧都有非負(fù)數(shù)，叫做該邊的容量。邊(vi,vj)的容量用cij表示。則稱之為網(wǎng)絡(luò)流圖，記為G=(V,E,C)可行流可行流 對于網(wǎng)絡(luò)流圖G，每一條弧(i,j)都給定一個非負(fù)數(shù)fij，這一組數(shù)滿足下列三條件時稱為這網(wǎng)絡(luò)的可行流，用f表示它。1.每一條弧(i,j)有fij≤Cij2.流量平衡 除源點(diǎn)S和匯點(diǎn)T以外的所有的點(diǎn)vi，恒有： ∑j(fij)=∑k(fjk)

該等式說明中間點(diǎn)vi的流量守恒，輸入與輸出量相等。3. 對于源點(diǎn)S和匯點(diǎn)T有， ∑i(fSi)=∑j(fjT)=V(f)可增廣路給定一個可行流f={fij}。若fij=Cij，稱<vi,vj>為飽和?。环駝t稱<vi,vj>為非飽和弧。若fij=0，稱<vi,vj>為零流弧；否則稱<vi,vj>為非零流弧。定義一條道路P，起點(diǎn)是S、終點(diǎn)是T。把P上所有與P方向一致的弧定義為正向弧，正向弧的全體記為P+；把P上所有與P方向相悖的弧定義為反向弧，反向弧的全體記為P-。譬如在圖中，P=(S,V1,V2,V3,V4,T)，那么

P+={<S,V1>,<V1,V2>,<V2,V3>,<V4,T>} P-={<V4,V3>}給定一個可行流f，P是從S到T的一條道路，如果滿足：

fij是非飽和流，并且<i,j>∈P+,fij是非零流，并且<i,j>∈P-

那么就稱P是f的一條可增廣路。之所以稱作“可增廣”，是因?yàn)榭筛倪M(jìn)路上弧的流量通過一定的規(guī)則修改，可以令整個流量放大。剩余圖(殘余網(wǎng)絡(luò))剩余圖G’=(V,E’)流量網(wǎng)絡(luò)G=(V,E)中，對于任意一條邊(a,b)，若flow(a,b)<capacity(a,b)orflow(b,a)>0則(a,b)∈E’可以沿著a--->b方向增廣2007冬令營講座剩余圖中，從源點(diǎn)到匯點(diǎn)的每一條路徑都對應(yīng)一條增廣路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向圖32224剩余圖剩余圖中，每條邊都可以沿其方向增廣剩余圖的權(quán)值代表能沿邊增廣的大小G=(V,E,C)是已知的網(wǎng)絡(luò)流圖，設(shè)U是V的一個子集，W=V\U，滿足S∈U，T∈W。即U、W把V分成兩個不相交的集合，且源點(diǎn)和匯點(diǎn)分屬不同的集合。對于弧尾在U，弧頭在W的弧所構(gòu)成的集合稱之為割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，記為C（U，W），即：割切割切示例上例中，令U={S,V1}，則W={V2,V3,V4,T}，那么，C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>=8+4+4+1=17流量算法的基本理論定理1：對于已知的網(wǎng)絡(luò)流圖，設(shè)任意一可行流為f，任意一割切為(U,W)，必有：V(f)≤C(U,W)。定理2：可行流f是最大流的充分必要條件是：f中不存在可改進(jìn)路。定理3：整流定理。 如果網(wǎng)絡(luò)中所有的弧的容量是整數(shù)，則存在整數(shù)值的最大流。定理4：最大流最小割定理。 最大流等于最小割，即maxV(f)=minC(U,W)。

最大流算法第1步，令x=(xij)是任意整數(shù)可行流，可能是零流，給s一個永久標(biāo)號(-,∞)。第2步(找增廣路)，如果所有標(biāo)號都已經(jīng)被檢查，轉(zhuǎn)到第4步。找到一個標(biāo)號但未檢查的點(diǎn)i,并做如下檢查，對每一個弧(i,j),如果xij<Cij,且j未標(biāo)號,則給j一個標(biāo)號(+i,δ(j)),其中，δ(j)=min{Cij-xij,δ(i)}對每一個弧(j,i),如果xji>0,且j未標(biāo)號，則給j一個標(biāo)號(-i,δ(j)),其中，δ(j)=min{xji,δ(i)}第3步(增廣)，由點(diǎn)t開始，使用指示標(biāo)號構(gòu)造一個增廣路,指示標(biāo)號的正負(fù)則表示通過增加還是減少弧流量來增加還是減少弧流量來增大流量，抹去s點(diǎn)以外的所有標(biāo)號，轉(zhuǎn)第二步繼續(xù)找增廣軌。第4步(構(gòu)造最小割)，這時現(xiàn)行流是最大的，若把所有標(biāo)號的集合記為S，所有未標(biāo)號點(diǎn)的集合記為T,便得到最小割(S,T)。實(shí)例復(fù)雜度分析設(shè)圖中弧數(shù)為m,每找一條增廣軌最多需要進(jìn)行2m次弧的檢查。如果所有弧的容量為整數(shù)，則最多需要v(其中v為最大流)次增廣，因此總的計算量為O(mv)。proceduremaxflow;{最大流}vari,j,delta,x:integer;last:tline;{可改進(jìn)路中的前趨}check:array[0..maxn]ofboolean;{檢查數(shù)組}beginrepeatfillchar(last,sizeof(last),0);fillchar(check,sizeof(check),false);last[1]:=maxint;repeati:=0;repeatinc(i)until(i>n)or(last[i]<>0)andnotcheck[i];{找到一個已檢查而未標(biāo)號的點(diǎn)}ifi>nthenbreak;forj:=1tondoiflast[j]=0thenifflow[i,j]<limit[i,j]thenlast[j]:=i{正向弧}elseifflow[j,i]>0thenlast[j]:=-i;{反向弧}check[i]:=true;untillast[n]<>0;

iflast[n]=0thenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifx<deltathendelta:=x;untili=1;{求改進(jìn)量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;{放大網(wǎng)絡(luò)流}untilfalse;end;利用找增廣路的其他流量算法增廣路的思想在于每次從源點(diǎn)搜索出一條前往匯點(diǎn)的增廣路，并改變路上的邊權(quán)，直到無法再進(jìn)行增廣：Ford-Fulkerson算法:在剩余圖中，采用深度優(yōu)先每次任意找一條增廣路徑增廣。O(k*nm)Edmonds-Karp算法:最短增廣路方法(SAP),在剩余圖中，用寬度優(yōu)先找一條含結(jié)點(diǎn)數(shù)最少的增廣路徑增廣。O(nm2)連續(xù)最短增廣路方法（DINIC）：Dinic算法要用到層次圖的數(shù)據(jù)結(jié)構(gòu)，即MSN(Multi-StageNetwork)。MSN可由每次計算得到的剩余網(wǎng)絡(luò)Gf再計算得到。在剩余圖中，每次BFS找增廣路徑時，記錄每個點(diǎn)的距離標(biāo)號。即一次標(biāo)號，多次增廣。O(n2m)DINIC算法層次圖：就是把原圖中的點(diǎn)按照到到源的距離分“層”，只保留不同層之間的邊的圖。算法流程

1、根據(jù)殘量網(wǎng)絡(luò)計算層次圖。

2、在層次圖中使用DFS進(jìn)行增廣直到不存在增廣路。

3、重復(fù)以上步驟直到無法增廣。時間復(fù)雜度因?yàn)樵贒inic的執(zhí)行過程中，每次重新分層，匯點(diǎn)所在的層次是嚴(yán)格遞增的，而n個點(diǎn)的層次圖最多有n層，所以最多重新分層n次。在同一個層次圖中，因?yàn)槊織l增廣路都有一個瓶頸，而兩次增廣的瓶頸不可能相同，所以增廣路最多m條。搜索每一條增廣路時，前進(jìn)和回溯都最多n次，所以這兩者造成的時間復(fù)雜度是O(nm)；而沿著同一條邊(i,j)不可能枚舉兩次，因?yàn)榈谝淮蚊杜e時要么這條邊的容量已經(jīng)用盡，要么點(diǎn)j到匯不存在通路從而可將其從這一層次圖中刪除。綜上所述，Dinic算法時間復(fù)雜度的理論上界是O(n2*m)。Maxflow-DinicDinic比之樸素的最大流算法作了幾點(diǎn)改動。①增加了一個用bfs標(biāo)號的操作，對于節(jié)點(diǎn)i的標(biāo)號dis[i]表示的是節(jié)點(diǎn)i到源點(diǎn)距離的下界（只有當(dāng)前邊的容量上限-已通過流量>0才可以拓展）②找增廣路時再加一個限制條件：只能由標(biāo)號為dis[i]的拓展到標(biāo)號為dis[i]+1的。③當(dāng)找不到增廣路時，重新標(biāo)號。當(dāng)匯點(diǎn)沒有標(biāo)號時，程序結(jié)束。DINIC算法演示：源點(diǎn)匯點(diǎn)422532匯點(diǎn)32對增廣路進(jìn)行增廣，增廣后退回到源點(diǎn)1匯點(diǎn)232匯點(diǎn)1找到增廣路路線，（紅色路線）找到增廣路路線，（紅色路線）對增廣路進(jìn)行增廣，增廣后退回到源點(diǎn)，再無增廣路線3Maxflow-Dinicvoidbh(){intstack[1001]={0},j,h,e,k;h=0;e=1;stack[1]=a[1]=1;while(h<e){h++;k=stack[h];for(j=1;j<=n;j++)if(c[k][j]-f[k][j]>0&&!hash[j)

{stack[++e]=j;hash[j]=1;dis[j]=dis[k]+1;}}}SAP:ShortestAugmentingPaths同Dinic有些類似的框架：①定義距離dis(i)為節(jié)點(diǎn)i到匯點(diǎn)距離的下界。②在初始距離標(biāo)號的基礎(chǔ)上，不斷沿可行弧找增廣路增廣，一般采用dfs。對于可行弧(i,j)有

dis[i]=dis[j]+1;③

遍歷當(dāng)前節(jié)點(diǎn)完成后，為了使下次再來的時候有路可走（當(dāng)然要滿足距離標(biāo)號的性質(zhì)：不超過真實(shí)距離），重標(biāo)號當(dāng)前節(jié)點(diǎn)為:

dis[i]=min{dis[j]|(i,j)}+1④當(dāng)源點(diǎn)的dis值>=總節(jié)點(diǎn)個數(shù)時算法結(jié)束。SAP:ShortestAugmentingPathsSAP還有一個很好很強(qiáng)大的優(yōu)化---GAP注意到我們在某次增廣后，最大流可能已經(jīng)求出，因此算法做了許多無用功?？梢园l(fā)現(xiàn)，距離標(biāo)號是單調(diào)增的。這啟示我們?nèi)绻麡?biāo)號中存在“間隙”，則圖中不會再有可增廣路，于是算法提前終止。實(shí)踐中我們使用數(shù)組sum[i]記錄標(biāo)號為i的頂點(diǎn)個數(shù)，若重標(biāo)號使得sum中原標(biāo)號項(xiàng)變?yōu)?，則停止算法。

事實(shí)上這并不是SAP獨(dú)有的優(yōu)化，，還有一種算法HLPP也與這二者有些相似，但是使用的相對少些，這里就不介紹了.用預(yù)流推進(jìn)辦法求網(wǎng)絡(luò)流預(yù)流推進(jìn)算法給每一個頂點(diǎn)一個標(biāo)號h(v)，表示該點(diǎn)到t的最短路（在殘量網(wǎng)絡(luò)中）。第一步hights()過程，就是BFS出初始最短路，計算出每一個頂點(diǎn)的h(v)。預(yù)流推進(jìn)算法的特征是運(yùn)用了預(yù)流來加快運(yùn)算。預(yù)流說明圖中的節(jié)點(diǎn)(除s,t)，僅需要滿足流入量>=流出量。其中流入量>流出量的結(jié)點(diǎn)，我們稱之為活動節(jié)點(diǎn)。我們的算法就是不斷地將活動結(jié)點(diǎn)，變?yōu)榉腔顒咏Y(jié)點(diǎn)，使得預(yù)流成為可行流。HLPP（HighestLabelPreflowPush)算法過程prepare()，即首先將與s相連的邊設(shè)為滿流，并將這時產(chǎn)生的活動結(jié)點(diǎn)加入隊(duì)列Q。這是算法的開始。以后便重復(fù)以下過程直到Q為空：(1).選出Q的一個活動頂點(diǎn)u。并依次判斷殘量網(wǎng)絡(luò)G'中每條邊(u,v)，若h(u)=h(v)+1，則順著這里條邊推流，直到Q變成非活動結(jié)點(diǎn)（不存在多余流量）。(Push推流過程)(2).如果u還是活動結(jié)點(diǎn)。則需要對u進(jìn)行重新標(biāo)號：h(u)=min{h(v)+1}，其中邊(u,v)存在于G'中。然后再將u加入隊(duì)列。(relable過程)可以證明，通過以上算法得到的結(jié)果就是最大流。預(yù)流推進(jìn)算法示例頂點(diǎn)u的通過量g(u)：剩余圖中，找入邊權(quán)和與出邊權(quán)和的較小值增廣時，每次找一個通過量最小的點(diǎn)v，從點(diǎn)v向源點(diǎn)“推”大小為g(v)的流量向匯點(diǎn)“拉”大小為g(v)的流量盡量使剩余圖中的邊飽和34578g(u)=12用預(yù)流推進(jìn)方法的一些網(wǎng)絡(luò)流算法預(yù)流推進(jìn)的算法核心思想是以邊為單元進(jìn)行推流操作：一般的預(yù)流推進(jìn)算法：在剩余圖中，維護(hù)一個預(yù)流，不斷對活躍點(diǎn)執(zhí)行push操作，或者relable操作來重新調(diào)整這個預(yù)流，直到不能操作。O(nm2)先進(jìn)先出預(yù)流推進(jìn)算法：在剩余圖中，以先進(jìn)先出隊(duì)列維護(hù)活躍點(diǎn)。O(n3)最高標(biāo)號預(yù)流推進(jìn)算法HLLP：在剩余圖中，每次檢查最高標(biāo)號的活躍點(diǎn)，需要用到優(yōu)先隊(duì)列。O(n2m1/2)費(fèi)用流流最重要的應(yīng)用是盡可能多的分流物資，這也就是我們已經(jīng)研究過的最大流問題。然而實(shí)際生活中，最大配置方案肯定不止一種，一旦有了選擇的余地，費(fèi)用的因素就自然參與到?jīng)Q策中來。右圖是一個最簡單的例子：弧上標(biāo)的兩個數(shù)字第一個是容量，第二個是費(fèi)用。這里的費(fèi)用是單位流量的花費(fèi)，譬如fs1=4，所需花費(fèi)為3*4=12。容易看出，此圖的最大流（流量是8）為：fs1=f1t=5,fs2=f2t=3。所以它的費(fèi)用是：3*5+4*5+7*3+2*3=62。(6,3)(5,4)(3,7)(8,2)STV1V2費(fèi)用流問題費(fèi)用流定義設(shè)有帶費(fèi)用的網(wǎng)絡(luò)流圖G=(V,E,C,W)，每條弧<Vi,Vj>對應(yīng)兩個非負(fù)整數(shù)Cij、Wij，表示該弧的容量和費(fèi)用。若流f滿足：流量V(f)最大。滿足a的前提下，流的費(fèi)用Cost(f)=∑<i,j>∈E(fij*Wij)最小。 就稱f是網(wǎng)絡(luò)流圖G的最小費(fèi)用最大流。最小費(fèi)用可改進(jìn)路 設(shè)P是流f的可改進(jìn)路，定義∑<vi,vj>∈P+Wij-∑<vi,vj>∈P-Wij

為P的費(fèi)用(為什么如此定義？)

如果P是關(guān)于f的可改進(jìn)路中費(fèi)用最小的，就稱P是f的最小費(fèi)用可改進(jìn)路。費(fèi)用流算法求最小費(fèi)用最大流的基本思想是貪心法。即：對于流f，每次選擇最小費(fèi)用可改進(jìn)路進(jìn)行改進(jìn)，直到不存在可改進(jìn)路為止。這樣的得到的最大流必然是費(fèi)用最小的。算法可描述為：第1步.令f為零流。第2步.若無最小費(fèi)用可改進(jìn)路，轉(zhuǎn)第5步；否則找到最小費(fèi)用可改進(jìn)路，設(shè)為P。第3步.根據(jù)P求delta（改進(jìn)量）。第4步.放大f。轉(zhuǎn)第2步。第5步.算法結(jié)束。此時的f即最小費(fèi)用最大流。如何求最小費(fèi)用可改進(jìn)路設(shè)帶費(fèi)用的網(wǎng)絡(luò)流圖G=(V,E,C,W)，它的一個可行流是f。我們構(gòu)造帶權(quán)有向圖B=(V’,E’)，其中：V’=V。若<Vi,Vj>∈E，fij<Cij，那么<Vi,Vj>∈E’，權(quán)為Wij。

若<Vi,Vj>∈E，fij>0，那么<Vj,Vi>∈E’，權(quán)為-Wij。顯然，B中從S到T的每一條道路都對應(yīng)關(guān)于f的一條可改進(jìn)路；反之，關(guān)于f的每條可改進(jìn)路也能對應(yīng)B中從S到T的一條路徑。即兩者存在一一映射的邏輯關(guān)系。故若B中不存在從S到T的路徑，則f必然沒有可改進(jìn)路；不然，B中從S到T的最短路徑即為f的最小費(fèi)用可改進(jìn)路。現(xiàn)在的問題變成：給定帶權(quán)有向圖B=(V’,E’)，求從S到T的一條最短路徑。迭代法求最短路經(jīng)考慮到圖中存在權(quán)值為負(fù)數(shù)的弧，不能采用Dijkstra算法；Floyd算法的效率又不盡如人意——所以，這里采用一種折衷的算法：迭代法（SPFA算法）。設(shè)Short[i]表示從S到i頂點(diǎn)的最短路徑長度；從S到頂點(diǎn)i的最短路徑中，頂點(diǎn)i的前趨記為Last[i]。那么迭代算法描述如下：（為了便于描述，令n=|V’|，S的編號為0，T的編號為n+1）step1.令Short[i]

+∞（1≤i≤n+1），Short[0]

0。step2.遍歷每一條弧<Vi,Vj>。若Short[i]+<i,j><Short[j]，則令Short[j]

Short[i]+<i,j>，同時Last[j]

i。重復(fù)做step2直到不存在任何任何弧滿足此條件為止。step3.算法結(jié)束。若Short[n+1]=+∞，則不存在從S到T的路徑；否則可以根據(jù)Last記錄的有關(guān)信息得到最短路徑。一次迭代算法的時間復(fù)雜度為O(kn2)，其中k是一個不大于n的變量。在費(fèi)用流的求解過程中，k大部分情況下都遠(yuǎn)小于n。procedurecostflow;{求最小費(fèi)用最大流}vari,j,x,delta:integer;best,last:tline;{best：最短路長度；last：可改進(jìn)路中的前趨頂點(diǎn)}more:boolean;beginrepeatfillword(best,sizeof(best)shr1,maxint);fillchar(last,sizeof(last),0);last[1]:=maxint;best[1]:=0;{賦初值}repeatmore:=false;fori:=1tondoifbest[i]<>maxintthenforj:=1tondobeginif(flow[i,j]<limit[i,j])and(best[i]+cost[i,j]<best[j])thenbeginbest[j]:=best[i]+cost[i,j];last[j]:=i;more:=true;end;

if(flow[j,i]>0)and(best[i]-cost[j,i]<best[j])thenbeginbest[j]:=best[i]-cost[j,i];last[j]:=-i;more:=true;end;end;untilnotmore;{找最優(yōu)可改進(jìn)路}ifbest[n]=maxintthenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifx<deltathendelta:=x;untili=1;{求改進(jìn)量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;untilfalse;{根據(jù)改進(jìn)量放大流}end;思維發(fā)散與探索可改進(jìn)路費(fèi)用：“遞增！遞增？” 設(shè)f從零流到最大流共被改進(jìn)了k次，每i次選擇的可改進(jìn)路的費(fèi)用為pi，那么會不會有p1≤p2≤p3≤……≤pk呢？迭代法：“小心死循環(huán)！嘿嘿……”

迭代法會出現(xiàn)死循環(huán)嗎？也就是說，構(gòu)造的帶權(quán)有向圖B中會存在負(fù)回路嗎？費(fèi)用：“你在乎我是負(fù)數(shù)嗎？”容量：“我管的可不僅是弧?！?網(wǎng)絡(luò)流圖中的“容量”都是對弧而言的，但若是給每個頂點(diǎn)也加上一個容量限制：即通過此頂點(diǎn)的流量的上限；任務(wù)仍然是求從S到T的最小費(fèi)用最大流。你能解決嗎？有上下界的最大流前面我們已經(jīng)了解了最大流問題，之中每條邊(u,v)都有一個容量上界c(u,v)，而現(xiàn)在我們將這個問題再變一下，對于每條邊又多了一個容量下界b(u,v)表示這條邊至少要流low(u,v)這么多的流量。顯然直接按照之前求最大流的方法，最后再判斷每條邊是否達(dá)到容量下界是。。。錯滴！有上下界的最大流重新看下前面的例子在這個例子中，它的最大流為10，而如果直接用dinic或者SAP求出來會發(fā)現(xiàn)最大流為16且滿足不了2→4這條邊的容量下界。有上下界的最大流首先我們考慮某些圖可能是不合法的，如下：

1→2至少要流3，而2→3最多只能流2.。所以我們首先要想辦法判斷一個圖是否是合法滴。

有上下界的最大流這里介紹一種簡易的方法來求解流量有上下界的網(wǎng)絡(luò)中網(wǎng)絡(luò)流問題:

AtFirst

c(u,v)

u到v的邊的流量上界。

b(u,v)u到v的邊流量下界。

st(u)

所有指向點(diǎn)u的邊的下界之和。

ed(u)

點(diǎn)u指向其他點(diǎn)的所有邊的下界之和。

s為源點(diǎn)，t為匯點(diǎn)。

有上下界的最大流Next構(gòu)造一個新網(wǎng)絡(luò)，設(shè)原網(wǎng)絡(luò)為G，新的網(wǎng)絡(luò)為D，D包含G中的所有點(diǎn)

構(gòu)造D的方法如下：

1.加入虛擬源點(diǎn)vs和虛擬匯點(diǎn)vt

2.若邊(u,v)屬于G那么這條邊也屬于D， cnew(u,v)=c(u,v)-b(u,v)

3.對于G中的每一個點(diǎn)v，D中加入邊 (vs,v),cnew(vs,v)=st(v)

4.對于G中的每一個點(diǎn)v，D中加入邊(v,vt), cnew(v,vt)=ed(v)

5.加入邊(t,s),cnew(t,s)=∞

6.tflow為所有邊的下界的和

有上下界的最大流構(gòu)圖示例有上下界的最大流判斷求出的最大流是否等于tflow，等于繼續(xù)，否則該圖不合法。在D中去掉所有和vs，vt相連的邊，注意，這里面去掉邊應(yīng)是雙向的都去掉，因?yàn)槲覀冊诟戮W(wǎng)絡(luò)時反向邊的c也會變化。去掉t到s的附加邊，注意這也應(yīng)該是雙向的。其他的邊不要改變。

在這個去掉邊之后的圖中接著運(yùn)行求