【正文】 j := i。 if last[j] 0 then x := limit[i, j] flow[i, j] else x := flow[j, i]。 until i = 1。 repeat j := i。 if last[j] 0 then inc(flow[i, j], delta) else dec(flow[j, i], delta)。 {放大網(wǎng)絡流 } until false。 利用找增廣路的其他流量算法 ? 增廣路的思想在于每次從源點搜索出一條前往匯點的增廣路，并改變路上的邊權(quán)，直到無法再進行增廣： ? 一般增廣路方法：在剩余圖中，每次 任意 找一條增廣路徑增廣。 O(nm*logU) ? 最短增廣路方法 (MPLA)：在剩余圖中，每次任意找一條 含結(jié)點數(shù)最少 的增廣路徑增廣。在距離標號最短路圖上，不斷 dfs找增廣路， 即一次標號，多次增廣 。 ? 第一步 hights()過程，就是 BFS出初始最短路，計算出每一個頂點的 h(v)。預流說明圖中的節(jié)點 (除 s, t)，僅需要滿足流入量 = 流出量。我們的算法就是不斷地將活動結(jié)點，變?yōu)榉腔顒咏Y(jié)點，使得預流成為可行流。這是算法的開始。并依次判斷殘量網(wǎng)絡 G39。(Push推流過程 ) ? (2).如果 u還是活動結(jié)點。 中。 (relable過程 ) ? 可以證明，通過以上算法得到的結(jié)果就是最大流。 O(nm2) ? 先進先出預流推進算法：在剩余圖中， 以先進先出隊列維護活躍點 。 O(n2m1/2) 費用流 ? 流最重要的應用是盡可能多的分流物資，這也就是我們已經(jīng)研究過的最大流問題。 ? 右圖是一個最簡單的例子：弧上標的兩個數(shù)字第一個是容量，第二個是費用。 ? 容易看出，此圖的最大流（流量是 8）為： fs1 = f1t = 5, fs2 = f2t = 3。 (6,3) (5,4) (3,7) (8,2) S T V1 V2 費用流問題 費用流定義 ? 設有帶費用的網(wǎng)絡流圖 G = (V, E, C, W)，每條弧 Vi, Vj對應兩個非負整數(shù) Cij、 Wij，表示該弧的容量和費用。 2. 滿足 a的前提下，流的費用 Cost(f) =∑ i,j∈E (fij * Wij)最小。 ? 最小費用可改進路 設 P是流 f的可改進路，定義 ∑ vi,vj∈P+ Wij ∑ vi,vj∈P Wij 為 P的費用 (為什么如此定義？ ) 如果 P是關(guān)于 f的可改進路中費用最小的，就稱 P是 f的最小費用可改進路 。即：對于流 f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。 ? 算法可描述為： ? 第 1步 . 令 f為零流。 ? 第 3步 . 根據(jù) P求 delta（改進量）。轉(zhuǎn)第 2步。此時的 f即最小費用最大流。我們構(gòu)造帶權(quán)有向圖 B = (V’, E’) ，其中： ? V’ = V 。 若 Vi, Vj∈E ， fij0，那么 Vj, Vi∈E’ ，權(quán)為 Wij。即兩者存在一一映射的邏輯關(guān)系。 ? 現(xiàn)在的問題變成：給定帶權(quán)有向圖 B = (V’, E’) ，求從 S到 T的一條最短路徑。 ? 設 Short[i]表示從 S到 i頂點的最短路徑長度；從 S到頂點 i的最短路徑中，頂點 i的前趨記為 Last[i]。 ? step 2. 遍歷每一條弧 Vi, Vj。重復做 step 2直到不存在任何任何弧滿足此條件為止。若 Short[n + 1]= +∞ ，則不存在從 S到 T的路徑；否則可以根據(jù) Last記錄的有關(guān)信息得到最短路徑。在費用流的求解過程中， k大部分情況下都遠小于 n。 {求最小費用最大流 } var i, j, x, delta : integer。 {best：最短路長度； last：可改進路中的前趨頂點 } more : boolean。 fillchar(last, sizeof(last), 0)。 best[1] := 0。 for i := 1 to n do if best[i] maxint then for j := 1 to n do begin if (flow[i, j] limit[i, j]) and (best[i] + cost[i, j] best[j]) then begin best[j] := best[i] + cost[i, j]。 more := true。 if (flow[j, i] 0) and (best[i] cost[j, i] best[j]) then begin best[j] := best[i] cost[j, i]。 more := true。 end。 {找最優(yōu)可改進路 } if best[n] = maxint then break。 i := n。 i := abs(last[j])。 if x delta then delta := x。 {求改進量 } i := n。 i := abs(last[j])。 until i = 1。 {根據(jù)改進量放大流 } end?！? 網(wǎng)絡流圖中的“容量”都是對弧而言的，但若是給每個頂點也加上一個容量限制：即通過此頂點的流量的上限；任務仍然是求從 S到 T的最小費用最大流。 ? 弧上數(shù)字對第一個是上界，第二個是下界。 (3,0) (3,0) (3,0) (3,0) (10,1) 原問題 3 3 3 3 0 (a) 3 2 2 3 1 (b) 增廣 怎樣找可行流 ? 一種自然的想法是去掉下界，將其轉(zhuǎn)化為只含上界的網(wǎng)絡流圖。具體方法如下： ? 設原網(wǎng)絡流圖為 G = (V, E, C, A)，構(gòu)造不含下界的網(wǎng)絡流圖 G’ = (V’, E’, C’) ： ’ = V∪{S’, T’} x，令 h(x)= ∑ vi,vx∈E AiX ，若 h(x)≠0 ，就添加一條弧 S’, x ，其上界為 h(x) 。 Vi, Vj∈E ，都有 Vi, Vj∈E’ ，其上界 C’ ij = Cij – Aij。 G’ 中以 S’ 為源點、 T’ 為匯點求得最大流 f’ 。否則可得原圖的一個可行流 f = f’ + A ，即所有的 fij = f’ ij + Aij 。 另外一種構(gòu)圖方法 ? C’ (u, v) = C(u, v) B(u, v) ? 設 ? 如果 M(i)非負，那么設一附加源 S0，則可以令 C’ (S0, i) = M(i)。 ? 在這樣一個加入附加源和附加匯的流網(wǎng)絡 C’ 中，如果任意 g(S0, i)或 g(i, T0)都達到滿載，那么 C’ 中的這一個可行流 g一定對應原網(wǎng)絡 G中的一個可行流 f；反之G中的任意一個可行流 f都可以對應 C’ 中的一個 g(S0, i)或 g(i, T0)都滿載的流。這樣的問題稱為多源點、多匯點最大流。 ? 增設一個“超級匯” T’ ，對每個匯點 Ti，新增弧 Ti,