【正文】 ? 其實這題的標準方法是貪心，但使用高效的網(wǎng)絡流算法節(jié)省了大部分的思考時間。 ? 問是否存在一種滿足條件的 01矩陣。 分析 ? ① s到用戶 i，容量為 Ci ② 用戶 i到中轉站 Ai和 Bi，容量為 ∞ ③中轉站 i到 t，容量為 Pi ? 考慮這個模型的割 割邊不可能是②中的邊，這保證了解的合法性 屬于①的割邊表示損失的利益 屬于③的割邊表示付出的代價 ? 顯然割的量越小越好，這樣這道題就轉換成一個最小割的問題 根據(jù)最大流最小割定理，設 sum=∑ Ci，我們只要求出該網(wǎng)絡的最大流 maxflow，則 summaxflow就是最大獲利 。 以下 M行，第 (i + 2)行的三個數(shù) Ai, Bi和 Ci描述第 i個用戶群的信息。（ 1≤ i≤ M, 1≤ Ai, Bi≤ N） ? THU集團的 CSamp。 ? 根據(jù) f易得最小割切（ U, W）（即最大流最小割定理） ? 那么選擇的項目集合就是 U，其最大收益即： ???}{\ SUi id最大收益思考題 4： 最大獲利 ? THU集團的 CSamp。 ? E中包含三類弧： 對所有的 i∈A ，存在弧 S, i，容量為 di。 ? 構造網(wǎng)絡流圖 G = (V, E, C)。第一個數(shù) ri表示第 i個項目共有多少前趨項目；接下來有 ri個正整數(shù) k1, k2, …, kri ，分別表示每個前趨項目的編號。 第 1行包含一個整數(shù) n（ 1≤n≤200 ）。這些項目就稱為第i個項目的“前趨項目”。證畢。 ? 若 Mij≠0 ，則存在弧 i, j和 j, i：其容量皆為 Mij；費用 Sji’ =Sij’ = ln(S ij)。那么 S0i = ASi， M0i = AMi；若間諜 i可以與敵軍司令部直接聯(lián)系 Si,n+1=1, Mi,n+1=+∞ ，否則 Si,n+1=0, Mi,n+1=0。 ? 輸出文件： 輸出文件中只有一行。 第三行 :n個整數(shù)，其中第 i（ i = 1, 2, …, n ）個整數(shù)如果為 0表示間諜 i與敵軍情報部不進行聯(lián)系，如果為 1則表示間諜與敵軍情報部進行聯(lián)系。 ? 你的任務是：擬定一個方案，確定消息應該從那些人手中傳遞到那些人手中，使得最終計劃的可靠性最大。 ? 對于一條消息，只有安全的通過了所有的中轉過程到達敵軍情報部，這個傳遞消息的過程才算安全的；因此根據(jù)乘法原理，它的安全程度 P就是從總部出發(fā)，經(jīng)多次傳遞直到到達敵軍那里，每一次傳遞該消息的安全程度的乘積。對于不和總部直接聯(lián)系的間諜，他的AMj=0（而表格中給出的他的 ASj是沒有意義的）。在給定的時間內(nèi)，任意兩人之間至多只進行一次點對點的雙人聯(lián)系。 6. Vi’, T （ 1≤i≤n ），容量為 ni，費用為 0。該弧的流量表示第 i天通過方式 c得到的毛巾數(shù)量。該弧的流量表示第 i天通過方式 a得到的毛巾數(shù)量。 V = {S, V1, V2, …, V n, V1’, V2’, …, V n’, T} ，其中 S是源點、 T是匯點。 ? 輸入文件：第 1行為 n, a, b, f, fA, fB. 第 2行為 n1, n2, …, n n（注： 1≤f, fA, fB≤60, 1≤n≤1000 ） ? 輸出文件：最少費用 4 1 2 3 2 1 38 8 2 1 6 分析 ? 公司第 i天需要 ni 塊毛巾，可以把這 ni 塊毛巾的來源列舉如下： 新買的毛巾。消毒方式有兩種， A種方式的消毒時間需要 a天時間， B中方式的消毒需要 b天時間（ ba），A種消毒方式的費用為每塊毛巾 fA， B種消毒方式的費用為每塊毛巾 fB，而買一塊新毛巾的費用為 f（新毛巾是已消毒的，當天可以使用）；而且 ffAfB。同時令原圖中弧的費用保持不變；新增弧的費用臵為 0。原圖中所有的弧予以保留，容量均為 +∞ 。 ? 對變換后的圖求最大流即可。 ? 將 f中的 S’ 和 T’ 去掉，即為原圖的最大流。這樣的問題稱為多源點、多匯點最大流。 另外一種構圖方法 ? C’ (u, v) = C(u, v) B(u, v) ? 設 ? 如果 M(i)非負，那么設一附加源 S0，則可以令 C’ (S0, i) = M(i)。 G’ 中以 S’ 為源點、 T’ 為匯點求得最大流 f’ 。具體方法如下： ? 設原網(wǎng)絡流圖為 G = (V, E, C, A)，構造不含下界的網(wǎng)絡流圖 G’ = (V’, E’, C’) ： ’ = V∪{S’, T’} x，令 h(x)= ∑ vi,vx∈E AiX ，若 h(x)≠0 ，就添加一條弧 S’, x ，其上界為 h(x) 。 ? 弧上數(shù)字對第一個是上界，第二個是下界。 {根據(jù)改進量放大流 } end。 i := abs(last[j])。 if x delta then delta := x。 i := n。 end。 if (flow[j, i] 0) and (best[i] cost[j, i] best[j]) then begin best[j] := best[i] cost[j, i]。 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]。 fillchar(last, sizeof(last), 0)。 {求最小費用最大流 } var i, j, x, delta : integer。若 Short[n + 1]= +∞ ，則不存在從 S到 T的路徑；否則可以根據(jù) Last記錄的有關信息得到最短路徑。 ? step 2. 遍歷每一條弧 Vi, Vj。 ? 現(xiàn)在的問題變成：給定帶權有向圖 B = (V’, E’) ，求從 S到 T的一條最短路徑。 若 Vi, Vj∈E ， fij0，那么 Vj, Vi∈E’ ，權為 Wij。此時的 f即最小費用最大流。 ? 第 3步 . 根據(jù) P求 delta（改進量）。即：對于流 f，每次選擇最小費用可改進路進行改進，直到不存在可改進路為止。 2. 滿足 a的前提下，流的費用 Cost(f) =∑ i,j∈E (fij * Wij)最小。 ? 容易看出，此圖的最大流（流量是 8）為： fs1 = f1t = 5, fs2 = f2t = 3。 O(n2m1/2) 費用流 ? 流最重要的應用是盡可能多的分流物資，這也就是我們已經(jīng)研究過的最大流問題。 (relable過程 ) ? 可以證明，通過以上算法得到的結果就是最大流。(Push推流過程 ) ? (2).如果 u還是活動結點。這是算法的開始。預流說明圖中的節(jié)點 (除 s, t)，僅需要滿足流入量 = 流出量。在距離標號最短路圖上，不斷 dfs找增廣路， 即一次標號，多次增廣 。 利用找增廣路的其他流量算法 ? 增廣路的思想在于每次從源點搜索出一條