mafia淺析ppt課件(編輯修改稿)
2025-06-06 23:39 本頁面
【文章內(nèi)容簡介】 。 ? 對于一些稀疏圖，預(yù)流推進(jìn)方法的實際效果往往不如增廣路方法。 增廣路徑方法求最大流 ? 偽碼表示如下（摘自 《 算法導(dǎo)論 》 ） : ? ************************************************************** ? FORDFULKERSON(G, s, t) ? 1 for each edge (u, v) ∈ E[G] ? 2 do f(u, v)← 0 ? 3 f(v, u)← 0 ? 4 while there exists a path p from s to t ? in the residual work Gf ? 5 do cf(p) ← min {cf(u, v) : (u, v) is in p} ? 6 for each edge (u, v) in p ? 7 do f(u, v) ← f(u, v) + cf(p) ? 8 f(v, u) ← f(u, v) ? ************************************************************** 算法實現(xiàn)細(xì)節(jié) 1. 網(wǎng)絡(luò)的轉(zhuǎn)換 ? 網(wǎng)絡(luò)的轉(zhuǎn)換在從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)的同時進(jìn)行， ? 將一個頂點(diǎn)拆分成兩個，頂點(diǎn) i為 v，頂點(diǎn)i+n為 v’； ? 同時將輸入的一條無向邊分為兩條有向邊。 ? 部分代碼如下： 算法實現(xiàn)細(xì)節(jié) ? ************************************************************** ? for (i=1。i=n。i++){ fincost。 ? (i,i+n,cost)。 //從 v到 v’的帶有該頂點(diǎn)權(quán)值的邊 ? (i+n,i,0)。 //容量為 0的逆向邊（ EK算法時用） ? } ? for (i=1。i=m。i++){ ? finv1v2。 //從頂點(diǎn) v1’到頂點(diǎn) v2的容量為無窮的邊 ? (v1+n,v2,1)。 //從頂點(diǎn) v2’到頂點(diǎn) v1的容量為無窮的邊 ? (v2+n,v1,1)； //容量為 0的逆向邊（ EK算法時用） ? (v1,v2+n,0)。 ? (v2,v1+n,0)。 ? } ? ***********************************************
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1