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 小鼠標 閱讀(312) |
評論 (0) 編輯
poj1273--網(wǎng)絡(luò)流
摘要: 最赤裸的網(wǎng)絡(luò)流，不斷找出增廣路增廣即可。找增廣路時，這里用的深度優(yōu)先搜索。
閱讀全文
posted @
2012-09-07 21:29 小鼠標 閱讀(289) |
評論 (1) 編輯
poj2488--回溯
摘要: 簡單說一下回溯法，回溯跟深度優(yōu)先遍歷是分不開的，我們傾向于把回溯看做深度優(yōu)先遍歷的延伸。我們知道，圖的深度優(yōu)先遍歷每個節(jié)點只會被訪問一次，因為我們一旦走過一個點，我們就會做相應(yīng)的標記，避免重復(fù)經(jīng)過同一個點。而回溯的做法是，當走過某一個點時，標記走過，并把該點壓棧；當該節(jié)點出棧時，我們再把它標記為沒有走過，這樣就能保證另外一條路也能經(jīng)過該點了
閱讀全文
posted @
2012-08-20 16:09 小鼠標 閱讀(446) |
評論 (0) 編輯
poj2386--圖的遍歷
摘要: 圖的常見遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷，他們的作用是將圖中的每個點都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長都相等（比如都是1）的話，深度優(yōu)先遍歷的過程是：
1.任意選定一個點p0作為遍歷的起點
2.從未訪問節(jié)點中任選一個距離p0最近的點進行訪問，并標記該點被訪問過
3.重復(fù)第2步，直到該連通分支中的所有節(jié)點都被訪問過
閱讀全文
posted @
2012-08-20 12:23 小鼠標 閱讀(1603) |
評論 (0) 編輯
zoj1060，poj1094--拓撲排序
摘要: 下面我先說以下拓撲排序：
嚴蔚敏《數(shù)據(jù)結(jié)構(gòu)》上的定義是：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
直觀的說偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
拓撲排序的具體做法是：
1.在有向圖中選擇一個沒有前驅(qū)（入度為0）的頂點，輸出
2.從圖中刪除該頂點和所有以它為尾的弧，并更新相關(guān)點的入度
3.重復(fù)1，2步，直到所有頂點都被輸出，或者發(fā)現(xiàn)圖中存在回路。
閱讀全文
posted @
2012-08-16 19:19 小鼠標 閱讀(1806) |
評論 (0) 編輯
單源最短路徑Dijkstra算法
摘要: dijkstra算法是解決單源最短路徑問題的經(jīng)典算法，具有O(N^2)的時間復(fù)雜度（N為節(jié)點個數(shù)），這種算法采用的是貪心策略，它與最小生成樹的Prim算法極其相似，這兩種算法僅僅是cost[]代表的含義不同……
閱讀全文
posted @
2012-08-08 16:27 小鼠標 閱讀(1879) |
評論 (0) 編輯