【正文】 ? C(U, W) = S, V2 + V1, V2 + V1, V3+V1, V4 =8+4+4+1=17 流量算法的基本理論 ? 定理 1：對于已知的網(wǎng)絡流圖，設任意一可行流為 f，任意一割切為 (U, W)，必有： V(f) ≤ C(U, W) 。若 fij = 0，稱 vi, vj為零流??；否則稱 vi, vj為非零流弧。 ? 若有向圖 G=(V,E)滿足下列條件： 1. 有且僅有一個頂點 S，它的入度為零，即 d(S) = 0，這個頂點 S便稱為源點，或稱為發(fā)點。 ? 每條弧代表一條公路，弧上的數(shù)表示該公路的最大運載量。 1. 每一條弧 (i,j)有 fij≤C ij 2. 流量平衡 除源點 S和匯點 T以外的所有的點 vi，恒有： ∑ j(fij)= ∑ k(fjk) 該等式說明中間點 vi的流量守恒，輸入與輸出量相等。 剩余圖 (殘余網(wǎng)絡 ) ? 剩余圖 G’=(V,E’) ? 流量網(wǎng)絡 G=(V,E)中，對于任意一條邊 (a,b)，若 ? flow(a,b)capacity(a,b) or flow(b,a)0 ? 則 (a,b)∈ E’ 可以沿著 ab方向增廣 ?剩余圖中，從源點到匯點的每一條路徑都對應一條增廣路 Capacity=5 Capacity=6 Capacity=2 Flow=2 Flow=2 Flow=2 有向圖 3 2 2 2 4 剩余圖 ?剩余圖中，每條邊都可以沿其方向增廣 剩余圖的權值代表能沿邊 增廣的大小 ? G = (V, E, C)是已知的網(wǎng)絡流圖，設 U是 V的一個子集，W = V\U，滿足 S ∈ U ， T∈W 。 最大流等于最小割，即 max V(f) = min C(U, W)。 {最大流 } var i, j, delta, x : integer。 {找到一個已檢查而未標號的點 } if i n then break。 i := abs(last[j])。 until i = 1。 O(n2m) DINIC算法演示： 源點 匯點 4 2 2 5 3 2 匯點 3 2 對增廣路進行增廣 ，增廣后退回到源點 1 匯點 2 3 2 匯點 1 找到增廣路路線 ，（ 紅色路線 ） 找到增廣路路線 ，（ 紅色路線 ） 對增廣路進行增廣 ，增廣后退回到源點 ，再無增廣路線 3 用預流推進辦法求網(wǎng)絡流 ? 預流推進算法給每一個頂點一個標號 h(v)，表示該點到 t的最短路（在殘量網(wǎng)絡中）。 ? 以后便重復以下過程直到 Q為空： ? (1).選出 Q的一個活動頂點 u。 預流推進算法示例 ? 頂點 u的通過量 g(u)： ? 剩余圖中，找入邊權和與出邊權和的較小值 ?增廣時，每次找一個通過量最小的點 v，從點 v ? 向源點“推”大小為 g(v)的流量 ? 向匯點“拉”大小為 g(v)的流量 ? 盡量使剩余圖中的邊飽和 3 4 5 7 8 g(u)=12 用預流推進方法的一些網(wǎng)絡流算法 ? 預流推進的算法核心思想是以邊為單元進行推流操作： ? 一般的預流推進算法：在剩余圖中， 維護一個預流 ，不斷對活躍點執(zhí)行 push操作，或者 relable操作來重新調整這個預流，直到不能操作。所以它的費用是： 3*5+4*5+7*3+2*3 = 62。這樣的得到的最大流必然是費用最小的。 如何求最小費用可改進路 ? 設帶費用的網(wǎng)絡流圖 G = (V, E, C, W)，它的一個可行流是 f。 迭代法求最短路經(jīng) ? 考慮到圖中存在權值為負數(shù)的弧，不能采用 Dijkstra算法；Floyd算法的效率又不盡如人意 —— 所以，這里采用一種折衷的算法：迭代法（ bellman算法）。 ? 一次迭代算法的時間復雜度為 O(kn2)，其中 k是一個不大于 n的變量。 last[1] := maxint。 last[j] := i。 repeat j := i。 if last[j] 0 then inc(flow[i, j], delta) else dec(flow[j, i], delta)。若是撇開下界不看，此圖的最大流如圖所示，流量是 6；但若是加入了下界的限制，它的最大流量就只有 5了。若 f’ 中從 S’發(fā)出的任意一條弧是非飽和弧，則原網(wǎng)絡流圖沒有可行流。 ? 它的解決很簡單： ? 增設一個“超級源” S’ ，對每個源點 Si，新增弧 S’, Si，容量為無窮大。 ? 這里我們運用到了化歸的思想：將未知的“點限制”問題轉化為已知的“邊限制”問題。然后以 S’ 為源點、 T’ 為匯點求最小費用最大流即可。 第 i – a – 1天之前通過 A種方式消毒的毛巾。 3. Vi, Via1’ （ a+2≤i≤n ），容量為正無窮大，費用為 fA。 ? 然后對這個網(wǎng)絡流圖以 S為源點、 T為匯點的求最小費用最大流即可。 ? 當然，假消息從間諜手中交到敵軍的情報部官員的辦公桌上的過程是絕對安全的，也就是說，間諜與敵軍情報部門之間要么不進行聯(lián)系，要么其聯(lián)系的安全程度是 1（即完全可靠）。 ? 輸入文件： 第一行 :兩個整數(shù) N和 K，分別是間諜的總人數(shù)和計劃包含的消息總數(shù)。這一行中包含一個實數(shù) P，給出的是整個計劃的可靠程度 P，保留 5位有效數(shù)字（四舍五入）。 ? 增設弧 n + 1, T，其容量為 k，費用為 0。 ? 現(xiàn)在給出所有項目的 ai、 bi，以及前趨項目。 ? 輸出文件： 輸出文件只有一個整數(shù) max，表示最大收益。 對所有的 i∈B ，存在弧 i, T，容量為 |di|。T公司可以有選擇的建立一些中轉站（投入成本），為一些用戶提供服務并獲得收益（獲益之和）。 構圖模型 ? 建立一張共有 n+m+2個的頂點、 3*m+n條邊的二分圖，求網(wǎng)絡的最大流。 。 ? 每一行、每一列最多可以有一個格子指定為 0。 第二行中有 N個整數(shù)描述每一個通訊中轉站的建立成本，依次為 P1, P2, …, P N 。 ? 然后對此網(wǎng)絡流圖求最大流，設為 f。則 di就是第i個項目的純收益， A是所有可以獲得利潤的項目集合， B是所有會導致虧損的項目集合。 ? 輸入文件： 輸入文件有 n + 3行。若流量小于 k，則不存在可行方案 ? 不然則最大可靠性為： ???? EjifijijS,證明 ? 設最大費用最大流的費用為 Cost，那么： ? 因為 Cost達到最大，所以可靠性也達到最大。（你可以假定，如果計劃存在，那么它的可靠性大于 1e12） ? 輸入輸出樣例 ? 6 13 0 0 0 2 6 8 0 0 0 0 0 0 1 0 1 1 4 2 2 3 5 2 5 2 2 6 7 3 5 2 5 6 4 1 1 分析 ? 題目中的“總部”、“敵軍情報部”與“間諜”的地位是完全相等的，為了方便敘述可以將兩者亦看作是間諜：“總部”編號為 0、“敵軍情報部”編號為 n+1。后 n個數(shù)是整數(shù) AM1, AM2,