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