最大流算法及其應(yīng)用-資料下載頁
2025-08-15 22:33本頁面
【正文】 二行中有 N個整數(shù)描述每一個通訊中轉(zhuǎn)站的建立成本，依次為 P1, P2, …, PN 。 ?以下 M行，第 (i + 2)行的三個數(shù) Ai, Bi和 Ci描述第 i個用戶群的信息。 ?所有變量的含義可以參見題目描述。 ?【 輸出格式 】 ?你的程序只要向輸出文件輸出一個整數(shù)，表示公司可以得到的最大凈獲利。 ?【 輸入樣例 】 ? 5 5 ? 1 2 3 4 5 ? 1 2 3 ? 2 3 4 ? 1 3 3 ? 1 4 2 ? 4 5 3 ?【 輸出樣例 】 ? 4 ?【 樣例說明 】 ?選擇建立 3號中轉(zhuǎn)站，則需要投入成本 6，獲利為 10，因此得到最大收益 4。 ?【 評分方法 】 ?本題沒有部分分，你的程序的輸出只有和我們的答案完全一致才能獲得滿分，否則不得分。 ?【 數(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。 分析 ?看到了“最大”這個字眼，很多人便以為此題與最小割沒有關(guān)系，但實(shí)際上不是。由于： ?凈獲利 = 獲益之和 投入成本之和 ? = 所有用戶群的獲益 （損失用戶群的獲益 + 建設(shè)中轉(zhuǎn)站的代價） ?要使凈獲利最大，即使（損失用戶群的獲益 + 建設(shè)中轉(zhuǎn)站的代價）最小，這就將“最大”變成了“最小”。 建模 ?下面建立流網(wǎng)絡(luò)，以每一個中轉(zhuǎn)站和用戶群為頂點(diǎn)，并增加源和匯。連接源到每個中轉(zhuǎn)站，容量為建設(shè)該中轉(zhuǎn)站的代價；連接每個用戶群到匯，容量為該用戶群的收益；對于每個用戶群，連接它的兩個相關(guān)中轉(zhuǎn)站到這個用戶群，容量為 ∞。由于割將所有的點(diǎn)分為 S和 T兩個集合，又因?yàn)槭亲钚「睿愿畹娜萘勘囟ú粫虚g那些容量為 ∞的弧，因此每個用戶群及其兩個相關(guān)的中轉(zhuǎn)站必定在一個集合中。那么 T中包含的中轉(zhuǎn)站便是我們選擇建設(shè)的， S中包含的用戶群即為放棄的用戶群。割的容量為源到所有 T中包含的中轉(zhuǎn)站的建設(shè)費(fèi)用和加上 S中包含的所有用戶的獲益和。又因?yàn)楦畹娜萘孔钚。越Y(jié)果最優(yōu)。 圖 4 樣例建成的流網(wǎng)絡(luò)（中間弧的容量均為 ∞） s t 1 2 3 4 5 3 4 3 2 3 實(shí)現(xiàn) ?最后再觀察數(shù)據(jù)范圍，可得流網(wǎng)絡(luò)的點(diǎn)數(shù)最多會有 55002（ 5000+50000+2）個，一般的最大流算法基本都是會超時的（雖然時限有 2s），但是用鄰接表的 SAP加上 Gap和當(dāng)前弧優(yōu)化是可以輕松 AC的。 四、總結(jié) ?網(wǎng)絡(luò)流算法越來越在信息學(xué)競賽中廣泛應(yīng)用，而且網(wǎng)絡(luò)流的建模一直是一個難點(diǎn)。在平時的練習(xí)中，我們還是要多做題，多見一些常見的模型，這樣才能在競賽時很快想起來網(wǎng)絡(luò)流的模型和算法。 ?總之，在學(xué)習(xí)中多練習(xí)和總結(jié)還是最重要的，只有這樣才能更快地提高水平。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1