poj2488--回溯
摘要: 簡單說一下回溯法，回溯跟深度優(yōu)先遍歷是分不開的，我們傾向于把回溯看做深度優(yōu)先遍歷的延伸。我們知道，圖的深度優(yōu)先遍歷每個節(jié)點只會被訪問一次，因為我們一旦走過一個點，我們就會做相應(yīng)的標記，避免重復(fù)經(jīng)過同一個點。而回溯的做法是，當走過某一個點時，標記走過，并把該點壓棧；當該節(jié)點出棧時，我們再把它標記為沒有走過，這樣就能保證另外一條路也能經(jīng)過該點了
閱讀全文
posted @
2012-08-20 16:09 小鼠標 閱讀(469) |
評論 (0) 編輯
poj2386--圖的遍歷
摘要: 圖的常見遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷，他們的作用是將圖中的每個點都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長都相等（比如都是1）的話，深度優(yōu)先遍歷的過程是：
1.任意選定一個點p0作為遍歷的起點
2.從未訪問節(jié)點中任選一個距離p0最近的點進行訪問，并標記該點被訪問過
3.重復(fù)第2步，直到該連通分支中的所有節(jié)點都被訪問過
閱讀全文
posted @
2012-08-20 12:23 小鼠標 閱讀(1619) |
評論 (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 小鼠標 閱讀(1824) |
評論 (0) 編輯
poj1014--01背包二進制拆分，空間壓縮
摘要: 01背包的狀態(tài)轉(zhuǎn)移方程為：
當v
當v>=Ci時f[i,v]=Max(f[i-1,v],f[i-1,v-Ci]+Wi);(2)//當?shù)趇件物品能夠放下時，我們可以選擇放，或不放，取決于總價值的大小。
其中v為當前背包的中容量，Ci表示第i件物品的體積，Wi表示第i件物品的價值，f[i,v]表示容量為v的背包在考慮前i件物品后的最大價值。 閱讀全文
posted @
2012-08-14 16:32 小鼠標 閱讀(1564) |
評論 (0) 編輯
zoj2971--英文轉(zhuǎn)換為數(shù)字
摘要: 題意描述：
我們知道英語描述數(shù)字與漢語是不同的，題目要求給出英文描述的數(shù)字，輸出實際的數(shù)字。
解題思路是，把所有關(guān)鍵字分成兩類，一類是“數(shù)字”，另一類是“權(quán)重”，遇到數(shù)字就加上去，遇到權(quán)重就乘上去，最后輸出結(jié)果就是了。不過這樣還不行，因為這會導(dǎo)致權(quán)重累計相乘，比如前面有一個million，要乘1000 000，后面又有一個thousand，還要乘1000，這顯然是不對的……
閱讀全文
posted @
2012-08-12 09:18 小鼠標 閱讀(1210) |
評論 (0) 編輯
單源最短路徑Dijkstra算法
摘要: dijkstra算法是解決單源最短路徑問題的經(jīng)典算法，具有O(N^2)的時間復(fù)雜度（N為節(jié)點個數(shù)），這種算法采用的是貪心策略，它與最小生成樹的Prim算法極其相似，這兩種算法僅僅是cost[]代表的含義不同……
閱讀全文
posted @
2012-08-08 16:27 小鼠標 閱讀(1892) |
評論 (0) 編輯
memset()和sizeof()
摘要: 數(shù)組初始化的時候常用for()循環(huán)，不過如果考慮效率的話，最好用memset()，下面簡單介紹以下memset()。
函數(shù)原型：
void *memset(void *s, int ch, size_t n)
函數(shù)解釋：將s中前n個字節(jié)替換為ch并返回s；
……
sizeof是C/C++中的一個操作符（operator），而不是函數(shù)……
閱讀全文
posted @
2012-08-07 23:38 小鼠標 閱讀(3205) |
評論 (2) 編輯