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