mafia淺析ppt課件(編輯修改稿)
2025-06-06 23:39 本頁面
【文章內(nèi)容簡介】 。 ? 對于一些稀疏圖，預流推進方法的實際效果往往不如增廣路方法。 增廣路徑方法求最大流 ? 偽碼表示如下（摘自 《 算法導論 》 ） : ? ************************************************************** ? 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)細節(jié) 1. 網(wǎng)絡的轉換 ? 網(wǎng)絡的轉換在從標準輸入讀入數(shù)據(jù)的同時進行， ? 將一個頂點拆分成兩個，頂點 i為 v，頂點i+n為 v’； ? 同時將輸入的一條無向邊分為兩條有向邊。 ? 部分代碼如下： 算法實現(xiàn)細節(jié) ? ************************************************************** ? for (i=1。i=n。i++){ fincost。 ? (i,i+n,cost)。 //從 v到 v’的帶有該頂點權值的邊 ? (i+n,i,0)。 //容量為 0的逆向邊（ EK算法時用） ? } ? for (i=1。i=m。i++){ ? finv1v2。 //從頂點 v1’到頂點 v2的容量為無窮的邊 ? (v1+n,v2,1)。 //從頂點 v2’到頂點 v1的容量為無窮的邊 ? (v2+n,v1,1)； //容量為 0的逆向邊（ EK算法時用） ? (v1,v2+n,0)。 ? (v2,v1+n,0)。 ? } ? ***********************************************
環(huán)評公示相關推薦
鄂ICP備17016276號-1