hdu3549--網(wǎng)絡(luò)流
摘要: 網(wǎng)絡(luò)流算法描述如下：
1.利用殘留網(wǎng)絡(luò)尋找增廣路
2.將這一條增廣路在圖中去除，并修改殘留網(wǎng)絡(luò)
3.重復(fù)1、2步，直到找不到殘留網(wǎng)絡(luò)
閱讀全文
posted @
2012-09-07 22:13 小鼠標(biāo) 閱讀(320) |
評(píng)論 (0) 編輯
poj1273--網(wǎng)絡(luò)流
摘要: 最赤裸的網(wǎng)絡(luò)流，不斷找出增廣路增廣即可。找增廣路時(shí)，這里用的深度優(yōu)先搜索。
閱讀全文
posted @
2012-09-07 21:29 小鼠標(biāo) 閱讀(300) |
評(píng)論 (1) 編輯
poj2488--回溯
摘要: 簡(jiǎn)單說(shuō)一下回溯法，回溯跟深度優(yōu)先遍歷是分不開的，我們傾向于把回溯看做深度優(yōu)先遍歷的延伸。我們知道，圖的深度優(yōu)先遍歷每個(gè)節(jié)點(diǎn)只會(huì)被訪問一次，因?yàn)槲覀円坏┳哌^一個(gè)點(diǎn)，我們就會(huì)做相應(yīng)的標(biāo)記，避免重復(fù)經(jīng)過同一個(gè)點(diǎn)。而回溯的做法是，當(dāng)走過某一個(gè)點(diǎn)時(shí)，標(biāo)記走過，并把該點(diǎn)壓棧；當(dāng)該節(jié)點(diǎn)出棧時(shí)，我們?cè)侔阉鼧?biāo)記為沒有走過，這樣就能保證另外一條路也能經(jīng)過該點(diǎn)了
閱讀全文
posted @
2012-08-20 16:09 小鼠標(biāo) 閱讀(468) |
評(píng)論 (0) 編輯
poj2386--圖的遍歷
摘要: 圖的常見遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷，他們的作用是將圖中的每個(gè)點(diǎn)都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長(zhǎng)都相等（比如都是1）的話，深度優(yōu)先遍歷的過程是：
1.任意選定一個(gè)點(diǎn)p0作為遍歷的起點(diǎn)
2.從未訪問節(jié)點(diǎn)中任選一個(gè)距離p0最近的點(diǎn)進(jìn)行訪問，并標(biāo)記該點(diǎn)被訪問過
3.重復(fù)第2步，直到該連通分支中的所有節(jié)點(diǎn)都被訪問過
閱讀全文
posted @
2012-08-20 12:23 小鼠標(biāo) 閱讀(1617) |
評(píng)論 (0) 編輯
單源最短路徑Dijkstra算法
摘要: dijkstra算法是解決單源最短路徑問題的經(jīng)典算法，具有O(N^2)的時(shí)間復(fù)雜度（N為節(jié)點(diǎn)個(gè)數(shù)），這種算法采用的是貪心策略，它與最小生成樹的Prim算法極其相似，這兩種算法僅僅是cost[]代表的含義不同……
閱讀全文
posted @
2012-08-08 16:27 小鼠標(biāo) 閱讀(1891) |
評(píng)論 (0) 編輯