【正文】 可。同時(shí)令原圖中弧的費(fèi)用保持不變；新增弧的費(fèi)用臵為 0。 ? 輸入文件：第 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 塊毛巾的來源列舉如下： 新買的毛巾。該弧的流量表示第 i天通過方式 a得到的毛巾數(shù)量。 6. Vi’, T （ 1≤i≤n ），容量為 ni，費(fèi)用為 0。對于不和總部直接聯(lián)系的間諜，他的AMj=0（而表格中給出的他的 ASj是沒有意義的）。 ? 你的任務(wù)是：擬定一個(gè)方案，確定消息應(yīng)該從那些人手中傳遞到那些人手中，使得最終計(jì)劃的可靠性最大。 ? 輸出文件： 輸出文件中只有一行。 ? 若 Mij≠0 ，則存在弧 i, j和 j, i：其容量皆為 Mij；費(fèi)用 Sji’ =Sij’ = ln(S ij)。這些項(xiàng)目就稱為第i個(gè)項(xiàng)目的“前趨項(xiàng)目”。第一個(gè)數(shù) ri表示第 i個(gè)項(xiàng)目共有多少前趨項(xiàng)目；接下來有 ri個(gè)正整數(shù) k1, k2, …, kri ，分別表示每個(gè)前趨項(xiàng)目的編號。 ? E中包含三類?。? 對所有的 i∈A ，存在弧 S, i，容量為 di。（ 1≤ i≤ M, 1≤ Ai, Bi≤ N） ? THU集團(tuán)的 CSamp。 分析 ? ① 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就是最大獲利 。 ? 其實(shí)這題的標(biāo)準(zhǔn)方法是貪心，但使用高效的網(wǎng)絡(luò)流算法節(jié)省了大部分的思考時(shí)間。 ? 問是否存在一種滿足條件的 01矩陣。 以下 M行，第 (i + 2)行的三個(gè)數(shù) Ai, Bi和 Ci描述第 i個(gè)用戶群的信息。 ? 根據(jù) f易得最小割切（ U, W）（即最大流最小割定理） ? 那么選擇的項(xiàng)目集合就是 U，其最大收益即： ???}{\ SUi id最大收益思考題 4： 最大獲利 ? THU集團(tuán)的 CSamp。 ? 構(gòu)造網(wǎng)絡(luò)流圖 G = (V, E, C)。 第 1行包含一個(gè)整數(shù) n（ 1≤n≤200 ）。證畢。那么 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)系。 ? 對于一條消息，只有安全的通過了所有的中轉(zhuǎn)過程到達(dá)敵軍情報(bào)部，這個(gè)傳遞消息的過程才算安全的；因此根據(jù)乘法原理，它的安全程度 P就是從總部出發(fā)，經(jīng)多次傳遞直到到達(dá)敵軍那里，每一次傳遞該消息的安全程度的乘積。在給定的時(shí)間內(nèi)，任意兩人之間至多只進(jìn)行一次點(diǎn)對點(diǎn)的雙人聯(lián)系。該弧的流量表示第 i天通過方式 c得到的毛巾數(shù)量。 V = {S, V1, V2, …, V n, V1’, V2’, …, V n’, T} ，其中 S是源點(diǎn)、 T是匯點(diǎn)。消毒方式有兩種， A種方式的消毒時(shí)間需要 a天時(shí)間， B中方式的消毒需要 b天時(shí)間（ ba），A種消毒方式的費(fèi)用為每塊毛巾 fA， B種消毒方式的費(fèi)用為每塊毛巾 fB，而買一塊新毛巾的費(fèi)用為 f（新毛巾是已消毒的，當(dāng)天可以使用）；而且 ffAfB。原圖中所有的弧予以保留，容量均為 +∞ 。 ? 將 f中的 S’ 和 T’ 去掉，即為原圖的最大流。 另外一種構(gòu)圖方法 ? C’ (u, v) = C(u, v) B(u, v) ? 設(shè) ? 如果 M(i)非負(fù)，那么設(shè)一附加源 S0，則可以令 C’ (S0, i) = M(i)。具體方法如下： ? 設(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) 。 {根據(jù)改進(jìn)量放大流 } end。 if x delta then delta := x。 end。 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]。 {求最小費(fèi)用最大流 } var i, j, x, delta : integer。 ? step 2. 遍歷每一條弧 Vi, Vj。 若 Vi, Vj∈E ， fij0，那么 Vj, Vi∈E’ ，權(quán)為 Wij。 ? 第 3步 . 根據(jù) P求 delta（改進(jìn)量）。 2. 滿足 a的前提下，流的費(fèi)用 Cost(f) =∑ i,j∈E (fij * Wij)最小。 O(n2m1/2) 費(fèi)用流 ? 流最重要的應(yīng)用是盡可能多的分流物資，這也就是我們已經(jīng)研究過的最大流問題。(Push推流過程 ) ? (2).如果 u還是活動(dòng)結(jié)點(diǎn)。預(yù)流說明圖中的節(jié)點(diǎn) (除 s, t)，僅需要滿足流入量 = 流出量。 利用找增廣路的其他流量算法 ? 增廣路的思想在于每次從源點(diǎn)搜索出一條前往匯點(diǎn)的增廣路，并改變路上的邊權(quán)，直到無法再進(jìn)行增廣： ? 一般增廣路方法：在剩余圖中，每次 任意 找一條增廣路徑增廣。 until i = 1。 until last[n] 0。 {檢查數(shù)組 } begin repeat fillchar(last, sizeof(last), 0)。 找到一個(gè)標(biāo)號但未檢查的點(diǎn) i, 并做如下檢查， ? 對每一個(gè)弧 (i,j),如果 xijCij, 且 j未標(biāo)號 ,則給 j一個(gè)標(biāo)號 (+i, δ (j) ),其中， δ (j)=min{Cijxij , δ (i) } ? 對每一個(gè)弧 (j, i),如果 xji0,且 j未標(biāo)號，則給 j一個(gè)標(biāo)號 (i, δ (j) ),其中， δ (j)=min{xji , δ (i) } ? 第 3步 (增廣 )，由點(diǎn) t開始，使用指示標(biāo)號構(gòu)造一個(gè)增廣路 ,指示標(biāo)號的正負(fù)則表示通過增加還是減少弧流量來增加還是減少弧流量來增大流量，抹去 s點(diǎn)以外的所有標(biāo)號，轉(zhuǎn)第二步繼續(xù)找增廣軌。把割切（ U， W）中所有弧的容量之和叫做此割切的容量，記為 C（ U， W），即： 割切 ????WjUiijcWUC ),(割切示例 ? 上例中，令 U = {S, V1}，則 W = {V2, V3, V4, T}，那么，