【正文】 前往匯點的增廣路，并改變路上的邊權(quán)，直到無法再進行增廣： ? 一般增廣路方法：在剩余圖中，每次 任意 找一條增廣路徑增廣。 if last[j] 0 then inc(flow[i, j], delta) else dec(flow[j, i], delta)。 until i = 1。 repeat j := i。 until last[n] 0。 repeat inc(i) until (i n) or (last[i] 0) and not check[i]。 {檢查數(shù)組 } begin repeat fillchar(last, sizeof(last), 0)。 procedure maxflow。 找到一個標(biāo)號但未檢查的點 i, 并做如下檢查， ? 對每一個弧 (i,j),如果 xijCij, 且 j未標(biāo)號 ,則給 j一個標(biāo)號 (+i, δ (j) ),其中， δ (j)=min{Cijxij , δ (i) } ? 對每一個弧 (j, i),如果 xji0,且 j未標(biāo)號，則給 j一個標(biāo)號 (i, δ (j) ),其中， δ (j)=min{xji , δ (i) } ? 第 3步 (增廣 )，由點 t開始，使用指示標(biāo)號構(gòu)造一個增廣路 ,指示標(biāo)號的正負則表示通過增加還是減少弧流量來增加還是減少弧流量來增大流量，抹去 s點以外的所有標(biāo)號，轉(zhuǎn)第二步繼續(xù)找增廣軌。 ? 定理 4：最大流最小割定理。把割切（ U， W）中所有弧的容量之和叫做此割切的容量，記為 C（ U， W），即： 割切 ????WjUiijcWUC ),(割切示例 ? 上例中，令 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) 。之所以稱作“可增廣”，是因為可改進路上弧的流量通過一定的規(guī)則修改，可以令整個流量放大。若 fij = 0，稱 vi, vj為零流??；否則稱 vi, vj為非零流弧。 ? 則稱之為網(wǎng)絡(luò)流圖，記為 G = (V, E, C) 可行流 可行流 對于網(wǎng)絡(luò)流圖 G，每一條弧 (i,j)都給定一個非負數(shù) fij，這一組數(shù)滿足下列三條件時稱為這網(wǎng)絡(luò)的可行流，用 f表示它。 ? 若有向圖 G=(V,E)滿足下列條件： 1. 有且僅有一個頂點 S，它的入度為零，即 d(S) = 0，這個頂點 S便稱為源點，或稱為發(fā)點。連接中轉(zhuǎn)站的是公路，每條公路都有最大運載量。 ? 每條弧代表一條公路，弧上的數(shù)表示該公路的最大運載量。 2. 有且僅有一個頂點 T，它的出度為零，即 d+(T) = 0，這個頂點 T便稱為匯點，或稱為收點。 1. 每一條弧 (i,j)有 fij≤C ij 2. 流量平衡 除源點 S和匯點 T以外的所有的點 vi，恒有： ∑ j(fij)= ∑ k(fjk) 該等式說明中間點 vi的流量守恒，輸入與輸出量相等。 ? 定義一條道路 P，起點是 S、終點是 T。 剩余圖 (殘余網(wǎng)絡(luò) ) ? 剩余圖 G’=(V,E’) ? 流量網(wǎng)絡(luò) G=(V,E)中，對于任意一條邊 (a,b)，若 ? flow(a,b)capacity(a,b) or flow(b,a)0 ? 則 (a,b)∈ E’ 可以沿著 ab方向增廣 ?剩余圖中，從源點到匯點的每一條路徑都對應(yīng)一條增廣路 Capacity=5 Capacity=6 Capacity=2 Flow=2 Flow=2 Flow=2 有向圖 3 2 2 2 4 剩余圖 ?剩余圖中，每條邊都可以沿其方向增廣 剩余圖的權(quán)值代表能沿邊 增廣的大小 ? G = (V, E, C)是已知的網(wǎng)絡(luò)流圖，設(shè) U是 V的一個子集，W = V\U，滿足 S ∈ U ， T∈W 。 ? 定理 2：可行流 f是最大流的充分必要條件是： f中不存在可改進路。 最大流等于最小割，即 max V(f) = min C(U, W)。 ? 第 4步 (構(gòu)造最小割 )，這時現(xiàn)行流是最大的，若把所有標(biāo)號的集合記為 S，所有未標(biāo)號點的集合記為 T,便得到最小割 (S,T)。 {最大流 } var i, j, delta, x : integer。 fillchar(check, sizeof(check), false)。 {找到一個已檢查而未標(biāo)號的點 } if i n then break。 if last[n] = 0 then break。 i := abs(last[j])。 {求改進量 } i := n。 until i = 1。 O(nmU) ? 容量縮放增廣路方法 :在剩余圖中，每次任意找一條 最大可增廣容量和 的增廣路徑增廣。 O(n2m) DINIC算法演示： 源點 匯點 4 2 2 5 3 2 匯點 3 2 對增廣路進行增廣 ，增廣后退回到源點 1 匯點 2 3 2 匯點 1 找到增廣路路線 ，（ 紅色路線 ） 找到增廣路路線 ，（ 紅色路線 ） 對增廣路進行增廣 ，增廣后退回到源點 ，再無增廣路線 3 用預(yù)流推進辦法求網(wǎng)絡(luò)流 ? 預(yù)流推進算法給每一個頂點一個標(biāo)號 h(v)，表示該點到 t的最短路（在殘量網(wǎng)絡(luò)中）。其中流入量 流出量的結(jié)點，我們稱之為活動節(jié)點。 ? 以后便重復(fù)以下過程直到 Q為空： ? (1).選出 Q的一個活動頂點 u。則需要對 u進行重新標(biāo)號：h(u) = min{h(v) + 1}，其中邊 (u,v)存在于 G39。 預(yù)流推進算法示例 ? 頂點 u的通過量 g(u)： ? 剩余圖中，找入邊權(quán)和與出邊權(quán)和的較小值 ?增廣時，每次找一個通過量最小的點 v，從點 v ? 向源點“推”大小為 g(v)的流量 ? 向匯點“拉”大小為 g(v)的流量 ? 盡量使剩余圖中的邊飽和 3 4 5 7 8 g(u)=12 用預(yù)流推進方法的一些網(wǎng)絡(luò)流算法 ? 預(yù)流推進的算法核心思想是以邊為單元進行推流操作： ? 一般的預(yù)流推進算法：在剩余圖中， 維護一個預(yù)流 ，不斷對活躍點執(zhí)行 push操作，或者 relable操作來重新調(diào)整這個預(yù)流，直到不能操作。然而實際生活中，最大配臵方案肯定不止一種，一旦有了選擇的余地，費用的因素就自然參與到?jīng)Q策中來。所以它的費用是： 3*5+4*5+7*3+2*3 = 62。 就稱 f是網(wǎng)絡(luò)流圖 G的最小費用最大流。這樣的得到的最大流必然是費用最小的。 ? 第 4步 . 放大 f。 如何求最小費用可改進路 ? 設(shè)帶費用的網(wǎng)絡(luò)流圖 G = (V, E, C, W)，它的一個可行流是 f。 ? 顯然， B中從 S到 T的每一條道路都對應(yīng)關(guān)于 f的一條可改進路；反之，關(guān)于 f的每條可改進路也能對應(yīng) B中從 S到 T的一條路徑。 迭代法求最短路經(jīng) ? 考慮到圖中存在權(quán)值為負數(shù)的弧，不能采用 Dijkstra算法；Floyd算法的效率又不盡如人意