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