poj2488--回溯
摘要: 簡單說一下回溯法，回溯跟深度優先遍歷是分不開的，我們傾向于把回溯看做深度優先遍歷的延伸。我們知道，圖的深度優先遍歷每個節點只會被訪問一次，因為我們一旦走過一個點，我們就會做相應的標記，避免重復經過同一個點。而回溯的做法是，當走過某一個點時，標記走過，并把該點壓棧；當該節點出棧時，我們再把它標記為沒有走過，這樣就能保證另外一條路也能經過該點了
閱讀全文
posted @
2012-08-20 16:09 小鼠標 閱讀(475) |
評論 (0) 編輯
poj2386--圖的遍歷
摘要: 圖的常見遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，他們的作用是將圖中的每個點都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長都相等（比如都是1）的話，深度優先遍歷的過程是：
1.任意選定一個點p0作為遍歷的起點
2.從未訪問節點中任選一個距離p0最近的點進行訪問，并標記該點被訪問過
3.重復第2步，直到該連通分支中的所有節點都被訪問過
閱讀全文
posted @
2012-08-20 12:23 小鼠標 閱讀(1625) |
評論 (0) 編輯
zoj1060，poj1094--拓撲排序
摘要: 下面我先說以下拓撲排序：
嚴蔚敏《數據結構》上的定義是：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
直觀的說偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
拓撲排序的具體做法是：
1.在有向圖中選擇一個沒有前驅（入度為0）的頂點，輸出
2.從圖中刪除該頂點和所有以它為尾的弧，并更新相關點的入度
3.重復1，2步，直到所有頂點都被輸出，或者發現圖中存在回路。
閱讀全文
posted @
2012-08-16 19:19 小鼠標 閱讀(1828) |
評論 (0) 編輯
zoj2971--英文轉換為數字
摘要: 題意描述：
我們知道英語描述數字與漢語是不同的，題目要求給出英文描述的數字，輸出實際的數字。
解題思路是，把所有關鍵字分成兩類，一類是“數字”，另一類是“權重”，遇到數字就加上去，遇到權重就乘上去，最后輸出結果就是了。不過這樣還不行，因為這會導致權重累計相乘，比如前面有一個million，要乘1000 000，后面又有一個thousand，還要乘1000，這顯然是不對的……
閱讀全文
posted @
2012-08-12 09:18 小鼠標 閱讀(1217) |
評論 (0) 編輯
單源最短路徑Dijkstra算法
摘要: dijkstra算法是解決單源最短路徑問題的經典算法，具有O(N^2)的時間復雜度（N為節點個數），這種算法采用的是貪心策略，它與最小生成樹的Prim算法極其相似，這兩種算法僅僅是cost[]代表的含義不同……
閱讀全文
posted @
2012-08-08 16:27 小鼠標 閱讀(1898) |
評論 (0) 編輯
memset()和sizeof()
摘要: 數組初始化的時候常用for()循環，不過如果考慮效率的話，最好用memset()，下面簡單介紹以下memset()。
函數原型：
void *memset(void *s, int ch, size_t n)
函數解釋：將s中前n個字節替換為ch并返回s；
……
sizeof是C/C++中的一個操作符（operator），而不是函數……
閱讀全文
posted @
2012-08-07 23:38 小鼠標 閱讀(3213) |
評論 (2) 編輯