最大流算法及其應(yīng)用-在線瀏覽
2024-09-25 22:33本頁面
【正文】 initialize flow f to 0 ?2 while there exists an augmenting path p ?3 do augment flow f along p ?4 return f 最小割問題 ?最小割是指流網(wǎng)絡(luò)中容量最小的割。（證明也在此略去） ?根據(jù)這個定理，我們就可以通過求流網(wǎng)絡(luò)的最大流來得到最小割。 ?這個方法的最大問題就在于怎樣快速地找到一條增廣路徑。 ?本文將重點介紹一種高效且實用的最大流算法： SAP算法 （最短增廣路算法）。并且引入距離標號的概念，可以在 O(n)的時間里找到一條最短增廣路。（此段中 n表示頂點數(shù) |V|， m表示邊數(shù) |E|） 距離標號 ?對于每個頂點 i賦予一個非負整數(shù)值 d(i)來描述 i到 t的“距離”遠近，稱它為距離標號，并且滿足以下兩個條件： ?d(t)=0 ?對于殘留網(wǎng)絡(luò) Gf中的一條弧 (i,j)， d(i)≤d(j)+1。顯然，允許路是殘留網(wǎng)絡(luò) Gf中的一條最短增廣路。 算法基本架構(gòu) ? Procedure Shortest_Augmenting_Path。 ? while d(s)n do ? begin ? if i出發(fā)有允許弧 (i,j) then ? begin ? 記錄 j在允許路上的前驅(qū)結(jié)點 i ? i:=j。 ? end。 //禁止以后再考慮頂點 i ? 當(dāng) i≠s時退回到前一步 ? end。 ? End。 Gap優(yōu)化 ?我們可以注意到由于殘留網(wǎng)絡(luò)的修改只會使 d(i)越來越大（因為修改前 d(i)d(j)+1，而修改后會存在d(i)=d(j)+1，因此變大了），所以說 d(i)是單調(diào)遞增的，這就提示我們，如果 d函數(shù)出現(xiàn)了“斷層”，即沒有 d(i)=k，而有 d(i)=177。我們可以這么想，現(xiàn)在的 i滿足d(i)=k+1，發(fā)現(xiàn)沒有一個 d(j)為 k，因此就會嘗試去調(diào)整 d(i)，但是 d(i)是單調(diào)遞增的，只會越來越大，所以 k這個空缺便永遠不會被補上，也就是說無法再找到增廣路徑。（因為 d(i)不變， d(j)不減且 d(i)≤d(j)+1）這樣，在查找允許弧的時候只需要從上一次找到的允許弧開始找。 SAP的兩個優(yōu)化效果比較 ?（程序 1： SAP 程序 2： SAP+Gap 程序 3：SAP+當(dāng)前弧 程序 4： SAP+Gap+當(dāng)前?。? ?測試題目： NOI2022《 最大獲利 》 比較結(jié)果（表中時間單位： s） 測試點1 測試點2 測試點3 測試點4 測試點5 測試點6 測試點7 測試點8 測試點9 程序 1 TLE TLE 程序 2 程序 3 TLE TLE 程序 4
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1