算法合集之淺析信息學(xué)中的“分”與“合”-資料下載頁(yè)
2025-10-09 18:36本頁(yè)面
【正文】 容量為 1，費(fèi)用為該元素的數(shù)值 value[i]，圖中包含源 S與匯 T。 ?所有點(diǎn) i向點(diǎn) (i+1)連邊，容量為 +∞ ，費(fèi)用為 0 ?源 S向所有點(diǎn) i各連一條邊，容量為 +∞，費(fèi)用為 0 ?所有點(diǎn) i’ 向匯 T各連一條邊，容量為 +∞，費(fèi)用為 0 ?所有點(diǎn) i’ 向點(diǎn) (i+M)連邊，容量為 +∞ ，費(fèi)用為 0 3’ 2’ 1’ …… n’ 1 2 3 n T S …… 容量 = 1 費(fèi)用 = value[i] +∞ 0 [例三 ]最優(yōu)序列 —— 整體分析 ?構(gòu)圖完成之后，網(wǎng)絡(luò)中的每個(gè)單位流量表示一個(gè)子問(wèn)題的解，因此，我們只需要在網(wǎng)絡(luò)中尋找 K次最大費(fèi)用增廣路即可得到答案。 ?由于這張圖的邊數(shù)與頂點(diǎn)數(shù)同階，若使用SPFA算法求增廣軌，則期望時(shí)間復(fù)雜度僅為 O(KN)，是個(gè)十分優(yōu)秀的算法。 總結(jié) 分 合 對(duì)立 統(tǒng)一 “ 分”的思想幫助我們迅速地切入問(wèn)題核心，但若過(guò)分細(xì)化則會(huì)使問(wèn)題太過(guò)凌亂，失去求解的方向；而“合”的思想則以線串珠，使各種紛雜無(wú)序的問(wèn)題具有了整體性。 謝 謝
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1