【正文】 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)部”與“間諜”的地位是完全相等的，為了方便敘述可以將兩者亦看作是間諜：“總部”編號(hào)為 0、“敵軍情報(bào)部”編號(hào)為 n+1。那么 S0i = ASi， M0i = AMi；若間諜 i可以與敵軍司令部直接聯(lián)系 Si,n+1=1, Mi,n+1=+∞ ，否則 Si,n+1=0, Mi,n+1=0。 ? 我們構(gòu)造帶費(fèi)用的網(wǎng)絡(luò)流圖 G = (V, E, M, S’) 。（ M為容量， S’位費(fèi)用） ? 第 i個(gè)間諜抽象成頂點(diǎn) i，另外增加匯點(diǎn) T。所有頂點(diǎn)構(gòu)成的集合記為 V。 ? 若 Mij≠0 ，則存在弧 i, j和 j, i：其容量皆為 Mij；費(fèi)用 Sji’ =Sij’ = ln(S ij)。 ? 增設(shè)弧 n + 1, T，其容量為 k，費(fèi)用為 0。 ? 然后以 V0為源點(diǎn)、 T為匯點(diǎn)求最大費(fèi)用最大流。若流量小于 k，則不存在可行方案 ? 不然則最大可靠性為： ???? EjifijijS,證明 ? 設(shè)最大費(fèi)用最大流的費(fèi)用為 Cost，那么： ? 因?yàn)?Cost達(dá)到最大，所以可靠性也達(dá)到最大。證畢。 C o s tSfEjifijEjiijijEjiijijeeSSfSfC o s tEjiijijij ?????????????????????,ln,ln39。可靠性思考題 3： Plan問(wèn)題 ? 某軟件公司有 n個(gè)可選的程序項(xiàng)目，其中第 i個(gè)項(xiàng)目需要耗費(fèi)資金 ai元，開(kāi)發(fā)成功后可獲收益 bi元。 ? 當(dāng)然，程序項(xiàng)目之間不是獨(dú)立的：開(kāi)發(fā)第 i個(gè)項(xiàng)目前，必須先開(kāi)發(fā)出一些其他的項(xiàng)目（正如開(kāi)發(fā) Office前必須開(kāi)發(fā) Windows）。這些項(xiàng)目就稱為第i個(gè)項(xiàng)目的“前趨項(xiàng)目”。 ? 現(xiàn)在給出所有項(xiàng)目的 ai、 bi，以及前趨項(xiàng)目。你的任務(wù)是：幫助該公司從這 n個(gè)程序項(xiàng)目中選擇若干個(gè)進(jìn)行開(kāi)發(fā)，使得總收益最大。 ? 輸入文件： 輸入文件有 n + 3行。 第 1行包含一個(gè)整數(shù) n（ 1≤n≤200 ）。 第 2行有 n個(gè)正整數(shù) a1, a2, …, an 。 第 3行有 n個(gè)正整數(shù) b1, b2, …, bn 。 第 i + 3行（ 1≤i≤n ）包含若干正整數(shù)： ri, k1, k2, …, kri 。第一個(gè)數(shù) ri表示第 i個(gè)項(xiàng)目共有多少前趨項(xiàng)目；接下來(lái)有 ri個(gè)正整數(shù) k1, k2, …, kri ，分別表示每個(gè)前趨項(xiàng)目的編號(hào)。 ? 輸出文件： 輸出文件只有一個(gè)整數(shù) max，表示最大收益。 分析 ? 令 di = bi – ai， A = {i | di ≥ 0} ， B = {i | di 0}。則 di就是第i個(gè)項(xiàng)目的純收益， A是所有可以獲得利潤(rùn)的項(xiàng)目集合， B是所有會(huì)導(dǎo)致虧損的項(xiàng)目集合。 ? 構(gòu)造網(wǎng)絡(luò)流圖 G = (V, E, C)。 ? V中包含兩類頂點(diǎn)： 源點(diǎn) S，匯點(diǎn) T。 將第 i個(gè)項(xiàng)目抽象成頂點(diǎn) Vi。則 V1, V2, …, V n∈V 。 ? E中包含三類?。? 對(duì)所有的 i∈A ，存在弧 S, i，容量為 di。 對(duì)所有的 i∈B ，存在弧 i, T，容量為 |di|。 若第 i個(gè)項(xiàng)目的某前趨項(xiàng)目編號(hào)為 j，則存在弧 i, j，容量為 +∞ 。 ? 然后對(duì)此網(wǎng)絡(luò)流圖求最大流，設(shè)為 f。 ? 根據(jù) f易得最小割切（ U, W）（即最大流最小割定理） ? 那么選擇的項(xiàng)目集合就是 U，其最大收益即： ???}{\ SUi id最大收益思考題 4： 最大獲利 ? THU集團(tuán)的 CSamp。T公司得到了一共 N個(gè)可以作為通訊信號(hào)中轉(zhuǎn)站的地址，建立第 i個(gè)通訊中轉(zhuǎn)站需要的成本為 Pi（ 1≤ i≤ N）。 ? 另外公司用戶群一共 M個(gè)。關(guān)于第 i個(gè)用戶群的信息概括為 Ai, Bi和 Ci：這些用戶會(huì)使用中轉(zhuǎn)站 Ai和中轉(zhuǎn)站 Bi進(jìn)行通訊，公司可以獲益 Ci。（ 1≤ i≤ M, 1≤ Ai, Bi≤ N） ? THU集團(tuán)的 CSamp。T公司可以有選擇的建立一些中轉(zhuǎn)站（投入成本），為一些用戶提供服務(wù)并獲得收益（獲益之和）。那么如何選擇最終建立的中轉(zhuǎn)站才能讓公司的凈獲利最大呢？（凈獲利 = 獲益之和 投入成本之和） 【 輸入格式 】 輸入文件中第一行有兩個(gè)正整數(shù) N和 M 。 第二行中有 N個(gè)整數(shù)描述每一個(gè)通訊中轉(zhuǎn)站的建立成本，依次為 P1, P2, …, P N 。 以下 M行，第 (i + 2)行的三個(gè)數(shù) Ai, Bi和 Ci描述第 i個(gè)用戶群的信息。 【 輸出格式 】 公司可以得到的最大凈獲利。 【 數(shù)據(jù)規(guī)模和約定 】 80%的數(shù)據(jù)中： N≤ 200， M≤ 1 000。 100%的數(shù)據(jù)中： N≤ 5 000， M≤ 50 000， 0≤ Ci≤ 100，0≤ Pi≤ 100。 分析 ? ① s到用戶 i，容量為 Ci ② 用戶 i到中轉(zhuǎn)站 Ai和 Bi，容量為 ∞ ③中轉(zhuǎn)站 i到 t，容量為 Pi ? 考慮這個(gè)模型的割 割邊不可能是②中的邊，這保證了解的合法性 屬于①的割邊表示損失的利益 屬于③的割邊表示付出的代價(jià) ? 顯然割的量越小越好，這樣這道題就轉(zhuǎn)換成一個(gè)最小割的問(wèn)題 根據(jù)最大流最小割定理，設(shè) sum=∑ Ci，我們只要求出該網(wǎng)絡(luò)的最大流 maxflow，則 summaxflow就是最大獲利 。 構(gòu)圖模型 ? 建立一張共有 n+m+2個(gè)的頂點(diǎn)、 3*m+n條邊的二分圖，求網(wǎng)絡(luò)的最大流。 匯點(diǎn) N個(gè)點(diǎn) M個(gè)點(diǎn) 源點(diǎn) 思考題 5：矩陣游戲 （ 2022年江蘇省選） ? 題目大意： ? 對(duì)于一個(gè) n行、 m列的 01矩陣，規(guī)定在第 i行中 1的個(gè)數(shù)恰為 Ri個(gè)（ 1=i=n）；在第 j列中 1的個(gè)數(shù)恰為 Cj個(gè)（ 1=j=m）。 ? 每一行、每一列最多可以有一個(gè)格子指定為 0。 ? 問(wèn)是否存在一種滿足條件的 01矩陣。 ? 數(shù)據(jù)范圍： n,m=1000 每個(gè)測(cè)試點(diǎn)最多 10組數(shù)據(jù)。 分析 ? 把第 i行作為點(diǎn) Xi，從 S至 Xi連一條邊，容量為 Ri ? 把第 j列作為點(diǎn) Yj，從 Yj至 T連一條邊，容量為 Cj ? 若第 i行第 j列可以放 1，那么從 Xi至 Yj連一條邊，容量為 1 ? 求網(wǎng)絡(luò)最大流，判斷流量值是否等于 1的總數(shù)即可 ? 邊的總數(shù)達(dá)到了 O(n*m) ? 使用 MPLA可以拿到 60%的分?jǐn)?shù) ? 使用 Dinic可以拿到 80%的分?jǐn)?shù) ? 首先不考慮指定為 0的格子； ? 因?yàn)閷⒛?2行或某 2列交換，不影響問(wèn)題的求解，我們不妨將 Ri與 Ci從大到小排序； ? 將多余的 1儲(chǔ)存起來(lái)； ? 第三列，需要 5個(gè) 1， 但只有 4行可以提供 1； 深入分析 結(jié)論 ? 加入這個(gè)簡(jiǎn)單的判斷后， MPLA算法仍然只能過(guò) 60%。 ? 但是 Dinic通過(guò)了 100%的數(shù)據(jù)。 ? 其實(shí)這題的標(biāo)準(zhǔn)方法是貪心，但使用高效的網(wǎng)絡(luò)流算法節(jié)省了大部分的思考時(shí)間。