連續(xù)擼了一整個(gè)清明假期的挑戰(zhàn)賽代碼終于結(jié)束了。作為比賽的最后店煞，做個(gè)小小的總結(jié)蟹演。
一些小感悟
寫代碼的時(shí)候，千萬不要為了方便隨意使用全局變量顷蟀，使用全局變量后酒请，代碼的耦合度大大提高。
對(duì)于這類比賽鸣个，能對(duì)特定的case進(jìn)行特定的編程或者調(diào)參羞反，對(duì)結(jié)果會(huì)有一定提升（可能會(huì)被禁止）。
對(duì)于每一次提交囤萤，保存好當(dāng)前的提交版本昼窗，使用git是一個(gè)不錯(cuò)的方案。
看不懂的代碼最好不要隨意復(fù)制涛舍，出了問題怎么改都不知道澄惊。
團(tuán)隊(duì)的互相協(xié)助，是在比賽中陷入僵局時(shí)的解藥富雅。
題目
求解思路
基本思路是最小費(fèi)用流+遺傳
在剛看到題目的時(shí)候掸驱，很容易發(fā)現(xiàn)這是一個(gè)最優(yōu)化問題，而且屬于NP-難問題没佑。因此我第一個(gè)想法就是毕贼，采用遺傳或者粒子群算法進(jìn)行求解，目標(biāo)函數(shù)根據(jù)題意很快就可以寫出图筹，我們使用費(fèi)用函數(shù)即可帅刀，但是卻不知道怎么個(gè)編碼让腹，對(duì)服務(wù)器編碼 or 網(wǎng)絡(luò)流編碼 or both。
直到我找到了最小費(fèi)用最大流算法扣溺，使用該算法骇窍，輸入服務(wù)器節(jié)點(diǎn)，即可計(jì)算出從服務(wù)器到滿足各個(gè)消費(fèi)節(jié)點(diǎn)需求的最小費(fèi)用網(wǎng)絡(luò)流路徑锥余。這樣腹纳，結(jié)合第一個(gè)思路，算法的整體框架就很明確了驱犹。我們先通過遺傳算法嘲恍，產(chǎn)生一堆服務(wù)器節(jié)點(diǎn)，然后將這些服務(wù)器節(jié)點(diǎn)輸入到最小費(fèi)用流算法中雄驹，得出各條路徑佃牛，通過路徑和服務(wù)器信息我們既可以得出該方案下的網(wǎng)絡(luò)費(fèi)用，將費(fèi)用作為遺傳算法的適應(yīng)度函數(shù)医舆，再使用遺傳算法中的變異俘侠、交叉、選擇等操作蔬将，選出優(yōu)秀的染色體爷速，然后返回最小費(fèi)用流算法，如此迭代循環(huán)霞怀。下面展示算法的流程圖惫东。
最大流、最小費(fèi)用算法
算法的具體過程這里我就不展開了毙石，放上比賽時(shí)廉沮，我們參考的一些文檔與網(wǎng)頁(yè)。
SPFA算法
SPFA是一種單源最短路徑算法胁黑。在這個(gè)題目中废封，我們使用了最小費(fèi)用流算法，網(wǎng)絡(luò)中存在負(fù)權(quán)邊丧蘸，大家熟知的Dijkstra算法便失去了用武之地。SPFA該上場(chǎng)了遥皂。
SPFA算法的詳細(xì)步驟力喷，看看下面這個(gè)鏈接就好了(⊙o⊙)SPFA 算法詳解( 強(qiáng)大圖解，不會(huì)都難演训！)
接下來我說說針對(duì)賽題的改進(jìn)策略弟孟。
首先，SPFA算法本身有兩種改進(jìn)策略：SLF 和 LLL
SLF：Small Label First 策略样悟，設(shè)要加入的節(jié)點(diǎn)是j拂募，隊(duì)首元素為i庭猩，若dist(j) < dist(i)，則將j插入隊(duì)首陈症，否則插入隊(duì)尾蔼水。
LLL：Large Label Last 策略，設(shè)隊(duì)首元素為i录肯，隊(duì)列中所有dist值的平均值為x趴腋，若dist(i)>x則將i插入到隊(duì)尾，查找下一元素论咏，直到找到某一i使得dist(i) <= x优炬，則將i出對(duì)進(jìn)行松弛操作。
SLF 可使速度提高 15 ~ 20%厅贪；SLF + LLL 可提高約 50%蠢护。
其次，我們?cè)谧钚≠M(fèi)用流使用SPFA算法時(shí)养涮，我們只需要知道是否存在從S到T的路徑糊余，而不必需要他們之間的最短路徑，因此单寂，我們?cè)谇蟮搅似渲械囊粭l路徑時(shí)dist != null贬芥，即可返回，不必繼續(xù)執(zhí)行宣决。
程序代碼
比賽的代碼我已經(jīng)放到GitHub上蘸劈，寫的比較糟糕，沒有優(yōu)化尊沸，請(qǐng)各位大佬輕噴+_+
