【正文】 樣盡快求源點 s到匯點 t的一個可行的最大流？ ? 在一個容量有上下界的流網(wǎng)絡 G中，怎樣盡快求源點 s到匯點 t的一個可行的最小流？ 多源點、多匯點的最大流 ? 已知網(wǎng)絡流圖有 n個源點 S S …… 、 Sn， m個匯點T T …… 、 Tm，求該圖的最大流。 ? 如果 M(i)非負，那么設一附加匯 T0，則可以令 C’ (S0, i) = M(i)。 （反向弧 Vi, Vj必須滿足 fij≥A ij，而非fij≥0 ），不斷放大 f，直到求出最大流。若 f’ 中從 S’發(fā)出的任意一條弧是非飽和弧，則原網(wǎng)絡流圖沒有可行流。 T, S∈E’ ，其上界 CTS = +∞ 。 x，令 h+(x)= ∑ vx,vj∈E AXi ，若 h+(x)≠0 ，就添加一條弧 x, T’ ，其上界為 h+(x) 。這種美好的愿望是可以實現(xiàn)的。若是撇開下界不看，此圖的最大流如圖所示，流量是 6；但若是加入了下界的限制，它的最大流量就只有 5了。你能解決嗎？ 有上下界的最大流 ? 上面討論的網(wǎng)絡流都只對每條弧都限定了上界（其實其下界可以看成 0），現(xiàn)在給每條弧 Vi, Vj加上一個下界限制 Aij (即必須滿足 Aij≤f ij)。 思維發(fā)散與探索 ? 可改進路費用：“遞增！遞增？” 設 f從零流到最大流共被改進了 k次，每 i次選擇的可改進路的費用為 pi，那么會不會有p1≤p 2≤p 3≤……≤p k呢？ ? 迭代法：“小心死循環(huán)！嘿嘿 ……” 迭代法會出現(xiàn)死循環(huán)嗎？也就是說，構造的帶權有向圖 B中會存在負回路嗎？ ? 費用：“你在乎我是負數(shù)嗎？” ? 容量：“我管的可不僅是弧。 until false。 if last[j] 0 then inc(flow[i, j], delta) else dec(flow[j, i], delta)。 repeat j := i。 until i = 1。 if last[j] 0 then x := limit[i, j] flow[i, j] else x := flow[j, i]。 repeat j := i。 delta := maxint。 until not more。 end。 last[j] := i。 end。 last[j] := i。 {賦初值 } repeat more := false。 last[1] := maxint。 begin repeat fillword(best, sizeof(best) shr 1, maxint)。 best, last : tline。 procedure costflow。 ? 一次迭代算法的時間復雜度為 O(kn2)，其中 k是一個不大于 n的變量。 ? step 3. 算法結束。若 Short[i] + i, j Short[j]，則令 Short[j] ? Short[i] + i, j，同時 Last[j] ? i。那么迭代算法描述如下：（為了便于描述，令 n = |V’| ， S的編號為 0， T的編號為 n+1） ? step 1. 令 Short[i] ? +∞ （ 1≤i≤n+1 ）， Short[0] ? 0。 迭代法求最短路經(jīng) ? 考慮到圖中存在權值為負數(shù)的弧，不能采用 Dijkstra算法；Floyd算法的效率又不盡如人意 —— 所以，這里采用一種折衷的算法：迭代法（ bellman算法）。 ? 故若 B中不存在從 S到 T的路徑，則 f必然沒有可改進路；不然， B中從 S到 T的最短路徑即為 f的最小費用可改進路。 ? 顯然， B中從 S到 T的每一條道路都對應關于 f的一條可改進路；反之，關于 f的每條可改進路也能對應 B中從 S到 T的一條路徑。 ? 若 Vi, Vj∈E ， fijCij，那么 Vi, Vj∈E’ ，權為 Wij。 如何求最小費用可改進路 ? 設帶費用的網(wǎng)絡流圖 G = (V, E, C, W)，它的一個可行流是 f。 ? 第 5步 . 算法結束。 ? 第 4步 . 放大 f。 ? 第 2步 . 若無最小費用可改進路，轉第 5步；否則找到最小費用可改進路，設為 P。這樣的得到的最大流必然是費用最小的。 費用流算法 ? 求最小費用最大流的基本思想是貪心法。 就稱 f是網(wǎng)絡流圖 G的最小費用最大流。若流 f滿足： 1. 流量 V(f)最大。所以它的費用是： 3*5+4*5+7*3+2*3 = 62。這里的費用是單位流量的花費，譬如 fs1=4，所需花費為 3*4=12。然而實際生活中，最大配臵方案肯定不止一種，一旦有了選擇的余地，費用的因素就自然參與到?jīng)Q策中來。 O(n3) ? 最高標號預流推進算法：在剩余圖中， 每次檢查最高標號的活躍點 ，需要用到優(yōu)先隊列。 預流推進算法示例 ? 頂點 u的通過量 g(u)： ? 剩余圖中，找入邊權和與出邊權和的較小值 ?增廣時，每次找一個通過量最小的點 v，從點 v ? 向源點“推”大小為 g(v)的流量 ? 向匯點“拉”大小為 g(v)的流量 ? 盡量使剩余圖中的邊飽和 3 4 5 7 8 g(u)=12 用預流推進方法的一些網(wǎng)絡流算法 ? 預流推進的算法核心思想是以邊為單元進行推流操作： ? 一般的預流推進算法：在剩余圖中， 維護一個預流 ，不斷對活躍點執(zhí)行 push操作，或者 relable操作來重新調整這個預流，直到不能操作。然后再將 u加入隊列。則需要對 u進行重新標號：h(u) = min{h(v) + 1}，其中邊 (u,v)存在于 G39。中每條邊 (u, v)，若 h(u) = h(v) + 1，則順著這里條邊推流，直到 Q變成非活動結點（不存在多余流量）。 ? 以后便重復以下過程直到 Q為空： ? (1).選出 Q的一個活動頂點 u。 預流推進算法流程 ? 算法過程 prepare()，即首先將與 s相連的邊設為滿流，并將這時產(chǎn)生的活動結點加入隊列 Q。其中流入量 流出量的結點，我們稱之為活動節(jié)點。 ? 預流推進算法的特征是運用了預流來加快運算。 O(n2m) DINIC算法演示： 源點 匯點 4 2 2 5 3 2 匯點 3 2 對增廣路進行增廣 ，增廣后退回到源點 1 匯點 2 3 2 匯點 1 找到增廣路路線 ，（ 紅色路線 ） 找到增廣路路線 ，（ 紅色路線 ） 對增廣路進行增廣 ，增廣后退回到源點 ，再無增廣路線 3 用預流推進辦法求網(wǎng)絡流 ? 預流推進算法給每一個頂點一個標號 h(v)，表示該點到 t的最短路（在殘量網(wǎng)絡中）。 O(nm2) ? 連續(xù)最短增廣路方法（ DINIC）：在剩余圖中，每次 BFS找增廣路徑增廣路徑時，記錄每個點的距離標號。 O(nmU) ? 容量縮放增廣路方法 :在剩余圖中，每次任意找一條 最大可增廣容量和 的增廣路徑增廣。 end。 until i = 1。 i := abs(last[j])。 {求改進量 } i := n。 if x delta then delta := x。 i := abs(last[j])。