prim演算法導論

A. prim演算法中，closedge[j].lowcost 是干什麼用的。新定點並入U後重新選擇最小邊。那段代碼沒看懂。 輔助

在看嚴蔚敏的這個prim演算法之前，我是看的《演算法導論》上的prim演算法，感覺那個更容易理解prim演算法，只是嚴的有相應的步驟，可以照著實現，網上好多實現prim演算法的，貌似也是基於這個。那個closedge[j].lowcost是用來記錄V到U-V的權值的（V是已經選擇的邊，U是所有的邊，U-V是剩下的邊），在這里可以找到V到U-V的最小權值。你手邊應該有書吧，那我就對著嚴的書說了，對於V1有V2，V3，V4分別是6，1，5，這時可以存入數組（對著那個P174的表），然後選了V3，這個時候就是需要更新closedge.lowcost，因為V2到V1是6而V2到V3是5，所以P175那邊的演算法倒數第六行的for循環就是用來更新這個的，因為對於新加入的點，可能會出現上面說的情況，其餘應該沒什麼問題的吧

B. 《演算法導論》（第三版）目錄

1.1 演算法

1.2 作為一種技術的演算法

2.1 插入排序

2.2 分析演算法

2.3 設計演算法

2.3.1 分治法

2.3.2 分析分治演算法

3.1 漸近記號

3.2 標准記號與常用函數

4.1 最大子數組問題

4.2 矩陣乘法的 Strassen 演算法

4.3 用代入法求解遞歸式

4.4 用遞歸樹方法求解遞歸式

4.5 用主方法求解遞歸式

*4.6 證明主定理

4.6.1 對 b 的冪證明主定理

4.6.2 向下取整和向上取整

5.1 僱傭問題

5.2 指示器隨機變數

5.3 隨機演算法

*5.4 概率分析和指示器隨機變數的進一步使用

5.4.1 生日悖論

5.4.2 球與箱子

5.4.3 特徵序列

5.4.4 在線僱傭問題

6.1 堆

6.2 維護堆的性質

6.3 建堆

6.4 堆排序演算法

6.5 優先隊列

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的隨機化版本

7.4 快速排序分析

7.4.1 最壞情況分析

7.4.2 期望運行時間

8.1 排序演算法的下界

8.2 計數排序

8.3 基數排序

8.4 桶排序

9.1 最小值和最大值

9.2 期望為線性時間的選擇演算法

9.3 最壞情況為線性時間的選擇演算法

10.1 棧和隊列

10.2 鏈表

10.3 指針和對象的實現

10.4 有根樹的表示

11.1 直接定址表

11.2 散列表

11.3 散列函數

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 開放定址法

11.5 完全散列

12.1 什麼是二叉樹

12.2 查詢二叉搜索樹

12.3 插入和刪除

12.4 隨機構建二叉搜索樹

13.1 紅黑樹的性質

13.2 旋轉

13.3 插入

13.4 刪除

14.1 動態順序統計

14.2 如何擴張數據結構

14.3 區間樹

15.1 鋼條切割

15.2 矩陣鏈乘法

15.3 動態規劃原理

15.4 最長公共子序列

15.5 最優二叉搜索樹

16.1 活動選擇問題

16.2 貪心演算法原理

16.3 赫夫曼編碼

*16.4 擬陣和貪心演算法

*16.5 用擬陣求解任務調度問題

17.1 聚合分析

17.2 核演算法

17.3 勢能法

17.4 動態表

17.4.1 表擴張

17.4.2 表擴張和收縮

18.1 B 樹的定義

18.2 B 樹上的基本操作

18.3 從 B 樹上刪除關鍵字

19.1 斐波那契結構

19.2 可合並堆操作

19.3 關鍵字減值和刪除一個結點

19.4 最大度數的界

20.1 基本方法

20.2 遞歸結構

20.2.1 原型 van Emde Boas 結構

20.2.2 原型 van Emde Boas 結構上的操作

20.3 van Emde Boas 樹及其操作

20.3.1 van Emde Boas 樹

20.3.2 van Emde Boas 樹的操作

21.1 不相交集合的操作

21.2 不相交集合的鏈表表示

21.3 不相交集合森林

*21.4 帶路徑壓縮的按秩合並的分析

22.1 圖的表示

22.2 廣度優先搜索

22.3 深度優先搜索

22.4 拓撲排序

22.5 強連通分量

23.1 最小生成樹的形成

23.2 Kruskal 演算法和 Prim 演算法

24.1 Bellman-Ford 演算法

24.2 有向無環圖中的單源最短路徑問題

24.3 Dijkstra 演算法

24.4 差分約束和最短路徑

24.5 最短路徑性質的證明

25.1 最短路徑和矩陣乘法

25.2 Floyd-Warshall 演算法

25.3 用於稀疏圖的 Johnson 演算法

26.1 流網路

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重貼標簽演算法

*26.5 前置重貼標簽演算法

27.1 動態多線程基礎

27.2 多線程矩陣乘法

27.3 多線程歸並排序

28.1 求解線性方程組

28.2 矩陣求逆

28.3 對稱正定矩陣和最小二乘逼近

29.1 標准型和鬆弛型

29.2 將問題表達為線性規劃

29.3 單純形演算法

29.4 對偶性

29.5 初始基本可行解

30.1 多項式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 實現

31.1 基礎數論概念

31.2 最大公約數

31.3 模運算

31.4 求解模線性方程

31.5 中國余數定理

31.6 元素的冪

31.7 RSA 公鑰加密系統

*31.8 素數的測試

*31.9 整數的因子分解

32.1 樸素字元串匹配演算法

32.2 Rabin-Karp 演算法

32.3 利用有限自動機進行字元串匹配

32.4 Knuth-Morris-Pratt 演算法

33.1 線段的性質

33.2 確定任意一對線段是否相交

33.3 尋找凸包

33.4 尋找最近點對

34.1 多項式時間

34.2 多項式時間的驗證

34.3 NP 完全性與可歸約性

34.4 NP 完全性的證明

34.5 NP 完全問題

34.5.1 團問題

34.5.2 頂點覆蓋問題

34.5.3 哈密頓迴路問題

34.5.4 旅行商問題

34.5.5 子集和問題

35.1 頂點覆蓋問題

35.2 旅行商問題

35.2.1 滿足三角不等式的旅行商問題

35.2.2 一般旅行商問題

35.3 集合覆蓋問題

35.4 隨機化和線性規劃

35.5 子集和問題

A.1 求和公式及其性質

A.2 確定求和時間的界

B.1 集合

B.2 關系

B.3 函數

B.4 圖

B.5 樹

B.5.1 自由樹

B.5.2 有根樹和有序樹

B.5.3 二叉樹和位置樹

C.1 計數

C.2 概率

C.3 離散隨機變數

C.4 幾何分布與二項分布

C.5 二項分布的尾部

D.1 矩陣與矩陣運算

D.2 矩陣的基本性質

C. 基礎-11：最小生成樹（MST）

最小生成樹（minimum spanning tree）是圖計算中基本的問題，背後的問題非常直接，假設無向連通圖G(V, E)，且E中的每條邊e有權值（可以表示距離、價值等），找出一顆樹，連接G中所有的邊，且連接這棵樹的所有邊的權值之和最小。在電子製造中，如何以最低的成本連接多個針管便是這一問題。

下面以一個圖來對此進行說明：

前面兩課中介紹了動態規劃和貪心演算法，都是用來解決最值問題，本文中的最小生成樹很顯然也屬於此類。最小生成樹使用貪心演算法，文中會對貪心演算法的使用進行說明。

假設mst是最終要求的最小生成樹，若A是最小生成樹mst邊集的子集，如果每次選擇一條邊(u, v)加入A，並且確保A始終是mst邊集的子集，則最終得到的A必然是mst最小生成樹的邊集。這樣的邊(u, v)稱為A的 安全邊 。安全邊即為可以選擇的邊。

為了得到安全邊，下面介紹一些概念。無向圖G=(V,E)的一個切割(S, V-S)是節點集V的一個劃分，如圖2所示：

顯然，一個切割將圖劃分為兩部分。如果一條邊(u,v)，u在S中，v在S-V中，則稱邊(u,v)橫跨切割(S, V-S)。如果集合A中不存在橫跨該切割的邊，則稱該切割尊重A；在橫跨切割的所有邊中，權重最小的邊稱為輕量級邊（註：輕量級邊可能不是唯一的）。

下面的定理和推論保證了Kruskal和Prim演算法的正確性，感興趣的童鞋可以自己證明或參考演算法導論中的說明。

根據定理1和推論1，構造最小生成樹可以有兩種方式，一種是切割的角度，一種是森林的角度。切割的角度：先從圖中選取一個點n ₁ ，劃一個切割({n ₁ }, V-{n ₁ })，然後找這個切割的輕量級邊以及這個邊在 V-{n ₁ }的節點n ₂ ；然後再劃一個切割（{n ₁ , n ₂ }, V-{n ₁ , n ₂ })，再找出對應的輕量級邊，...,直到所有的節點，每一步中找到的輕量級邊組成的集合為最小生成樹中的邊。

森林的方式是：首先將每個節點都看成一個連通分量（此時有n個連通分量），尋找連通連接連通分量權值最小的邊(u, v)，(u, v)連接的連通分量為C ₁ 和C ₂ ，則(u, v)連接後，合成一個更大的連通分量C ₁₂ （此時有n-1個連通分量）；然後對n-1個連通分量繼續實施上述類似的動作，直至最後變成一個連通分量。

切割的角度對應的是Prim演算法，森林的方式對應的是Kruskal演算法，演算法本身都很簡單，在此不再贅述，下面兩組從演算法導論中摘取的圖很好地解釋了對應的演算法。

最小生成樹是圖計算中的基本演算法，理解演算法的關鍵是切割基礎上的輕量級邊，上文的說明中野間接解釋了利用貪心演算法的正確性，相對而言，最小生成樹是較為簡單和基礎的演算法，是其他演算法的基礎。

D. 演算法怎麼學

貪心演算法的定義：

貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，只做出在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

解題的一般步驟是：

1.建立數學模型來描述問題；

2.把求解的問題分成若干個子問題；

3.對每一子問題求解，得到子問題的局部最優解；

4.把子問題的局部最優解合成原來問題的一個解。

如果大家比較了解動態規劃，就會發現它們之間的相似之處。最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。

話不多說，我們來看幾個具體的例子慢慢理解它：

1.活動選擇問題

這是《演算法導論》上的例子，也是一個非常經典的問題。有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。例如下圖所示的活動集合S，其中各項活動按照結束時間單調遞增排序。

關於貪心演算法的基礎知識就簡要介紹到這里，希望能作為大家繼續深入學習的基礎。

E. 圖的相關演算法（二）：最小生成樹演算法

在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，並使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。

例如，對於上圖中的連通網可以有多棵權值總和不相同的生成樹。

克魯斯卡爾（Kruskal）演算法，是用來求加權連通圖的最小生成樹的演算法。

基本思想 ：按照權值從小到大的順序選擇n-1條邊，並保證這n-1條邊不構成迴路。
具體做法 ：首先構造一個只含n個頂點的森林，然後依照權值從小到大從連通網中選擇邊加入到森林中，並使得森林不產生迴路，直到森林變成一棵樹為止。

以圖G4為例（更詳細的可以參考《演算法導論》p367），對Kruskal進行演示（假設，用數組R保存最小生成樹結果）。

第1步 ：將邊<E,F>加入R中。
邊<E,F>的權值最小，因此將它加入到最小生成樹結果R中。
第2步 ：將邊<C,D>加入R中。
上一步操作之後，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中。
第3步 ：將邊<D,E>加入R中。
上一步操作之後，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中。
第4步 ：將邊<B,F>加入R中。
上一步操作之後，邊<C,E>的權值最小，但<C,E>會和已有的邊構成迴路；因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結果R中。
第5步 ：將邊<E,G>加入R中。
上一步操作之後，邊<E,G>的權值最小，因此將它加入到最小生成樹結果R中。
第6步 ：將邊<A,B>加入R中。
上一步操作之後，邊<F,G>的權值最小，但<F,G>會和已有的邊構成迴路；因此，跳過邊<F,G>。同理，跳過邊<B,C>。將邊<A,B>加入到最小生成樹結果R中。

此時，最小生成樹構造完成！它包括的邊依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。

根據前面介紹的克魯斯卡爾演算法的基本思想和做法，我們能夠了解到，克魯斯卡爾演算法重點需要解決的以下兩個問題：
問題一 對圖的所有邊按照權值大小進行排序。
問題二 將邊添加到最小生成樹中時，怎麼樣判斷是否形成了迴路。

問題一用排序演算法排序即可。
問題二，處理方式：記錄頂點在「最小生成樹」中的終點，頂點的終點是「在最小生成樹中與它連通的最大頂點"(關於這一點，後面會通過圖片給出說明)。然後每次需要將一條邊添加到最小生成樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成迴路。 以下圖來進行說明：

在將<E,F> <C,D> <D,E>加入到最小生成樹R中之後，這幾條邊的頂點就都有了終點：

關於終點，就是將所有頂點按照從小到大的順序排列好之後；某個頂點的終點就是"與它連通的最大頂點"。 因此，接下來，雖然<C,E>是權值最小的邊。但是C和E的重點都是F，即它們的終點相同，因此，將<C,E>加入最小生成樹的話，會形成迴路。這就是判斷迴路的方式。

普里姆（Prim）演算法，也是求加權連通圖的最小生成樹的演算法。

基本思想
對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。從所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有頂點）的邊中選取權值最小的邊（u，v），將頂點v加入U中，將邊（u,v）加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，此時集合T中包含了最小生成樹中的所有邊。

以上圖G4為例，來對普里姆進行演示(從第一個頂點A開始通過普里姆演算法生成最小生成樹)。

初始狀態 ：V是所有頂點的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：將頂點A加入到U中。
此時，U={A}。
第2步 ：將頂點B加入到U中。
上一步操作之後，U={A}, V-U={B,C,D,E,F,G}；因此，邊(A,B)的權值最小。將頂點B添加到U中；此時，U={A,B}。
第3步 ：將頂點F加入到U中。
上一步操作之後，U={A,B}, V-U={C,D,E,F,G}；因此，邊(B,F)的權值最小。將頂點F添加到U中；此時，U={A,B,F}。
第4步 ：將頂點E加入到U中。
上一步操作之後，U={A,B,F}, V-U={C,D,E,G}；因此，邊(F,E)的權值最小。將頂點E添加到U中；此時，U={A,B,F,E}。
第5步 ：將頂點D加入到U中。
上一步操作之後，U={A,B,F,E}, V-U={C,D,G}；因此，邊(E,D)的權值最小。將頂點D添加到U中；此時，U={A,B,F,E,D}。
第6步 ：將頂點C加入到U中。
上一步操作之後，U={A,B,F,E,D}, V-U={C,G}；因此，邊(D,C)的權值最小。將頂點C添加到U中；此時，U={A,B,F,E,D,C}。
第7步 ：將頂點G加入到U中。
上一步操作之後，U={A,B,F,E,D,C}, V-U={G}；因此，邊(F,G)的權值最小。將頂點G添加到U中；此時，U=V。

此時，最小生成樹構造完成！它包括的頂點依次是：A B F E D C G。

F. 關於prim演算法的時間復雜度

Prim演算法的時間復雜度與網中的邊數無關，適合於稠密圖。

通過鄰接矩陣圖表示的簡易實現中，找到所有最小權邊共需O（V）的運行時間。使用簡單的二叉堆與鄰接表來表示的話，普里姆演算法的運行時間則可縮減為O(ElogV)，其中E為連通圖的邊數，V為頂點數。

如果使用較為復雜的斐波那契堆，則可將運行時間進一步縮短為O(E+VlogV)，這在連通圖足夠密集時（當E滿足Ω（VlogV）條件時），可較顯著地提高運行速度。

(6)prim演算法導論擴展閱讀：

演算法描述：

1、輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；

2、初始化：Vnew= {x}，其中x為集合V中的任一節點（起始點），Enew= {},為空；

3、重復下列操作，直到Vnew= V：

在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，並且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

將v加入集合Vnew中，將<u, v>邊加入集合Enew中；

4、輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。

G. 哪些常見演算法屬於貪婪演算法

顯然KMP和FLOYD演算法不是貪心演算法，FLOYD演算法是使用了類似於動態規劃的思想，而KMP演算法則是對串的前綴進行去處理得到所有可能出現匹配的位置從而減少不必要的位移。貪心演算法可能還有很多，但是一般能用到的可能只有這些。在確定一個問題是否能用貪心來解決的時候應該線能夠證明在這里使用貪心演算法的正確性（詳見演算法導論）

H. 程序員如何學好演算法

一.基本演算法:

枚舉. (poj1753,poj2965)

貪心(poj1328,poj2109,poj2586)

遞歸和分治法.

遞推.

構造法.(poj3295)

模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖演算法:

圖的深度優先遍歷和廣度優先遍歷.

最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)

二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)

最大流的增廣路演算法(KM演算法). (poj1459,poj3436)

三.數據結構.

串 (poj1035,poj3080,poj1936)

排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)

簡單並查集的應用.

哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)

堆

trie樹(靜態建樹、動態建樹) (poj2513)

四.簡單搜索

深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態規劃

背包問題. (poj1837,poj1276)

型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學

組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.

幾何公式.

叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中級（校賽壓軸及省賽中等難度）:
一.基本演算法:

C++的標准模版庫的應用. (poj3096,poj3007)

較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖演算法:

差分約束系統的建立和求解. (poj1201,poj2983)

最小費用最大流(poj2516,poj2516,poj2195)

雙連通分量(poj2942)

強連通分支及其縮點.(poj2186)

圖的割邊和割點(poj3352)

最小割模型、網路流規約(poj3308)

三.數據結構.

線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

靜態二叉檢索樹. (poj2482,poj2352)

樹狀樹組(poj1195,poj3321)

RMQ. (poj3264,poj3368)

並查集的高級應用. (poj1703,2492)

KMP演算法. (poj1961,poj2406)

四.搜索

最優化剪枝和可行性剪枝

搜索的技巧和優化 (poj3411,poj1724)

記憶化搜索(poj3373,poj1691)

五.動態規劃

較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)

樹型動態規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.

坐標離散化.

掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)

幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級（regional中等難度）:
一.基本演算法要求:

代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保證正確性和高效性. poj3434

二.圖演算法:

度限制最小生成樹和第K最短路. (poj1639)

最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)

最小樹形圖(poj3164)

次小生成樹.

無向圖、有向圖的最小環

三.數據結構.

trie圖的建立和應用. (poj2778)

LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).

後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索

較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)

五.動態規劃

需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.

較難的狀態DP(poj3133)

六.數學

組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.

半平面求交(poj3384,poj2540)

可視圖的建立(poj2966)

點集最小圓覆蓋.

對踵點(poj2079)

I. 什麼是科研人員應該具有的能力，什麼是工程師應該具有的能力

這幾天，由於項目工作需要暫停，所以我就抽空開始學《演算法導論》。認為這是一本很不錯的書，不僅介紹了各種演算法，而且給出了演算法的由來（它的發明者是如何想到它的），以及效率的數學計算，當然還包含了演算法的數學基礎。我覺得這本書應該很耐看。它不向目前的一些國內的演算法教材，只是羅列些經典演算法，讓你應用的時候可以想到去套這些演算法。 昨天晚上和大師兄說了我正在學演算法導論的事情。本以為大師兄會很支持，結果大師兄說，其實科研人員並不關心演算法效率的問題，只有程序員或編程高手才會更關心效率的問題。 比如我曾經用C語言和MATLAB同時實現prim和kruskal演算法，由於matlab語言對矩陣的特殊支持，matlab實現的演算法顯然比C語言高。 我們在本科多是工程上的訓練。其目的就是：以後無論那門編程語言，只要學一個星期就能上手。。 可是當我在考研面試的時候，說道不同的編程語言對實現不同的演算法有不同的效率時，在場的老師不屑一顧。當我能使用多種編程語言。又有人認為編程只是一種工具罷了，我充其量只不過是一個木匠。當人家問我資料庫知識，我答出一小部分時，有人有任務我沒有理論素養。。荒謬，真是荒謬。。。 我承認在本科，我們受到的訓練都是工程上的訓練，其目的是深刻的認識「編程語言只是工具，不是限制人思維的桎梏」。不學幾種語言，怎麼能深刻認識到這樣一點，怎麼能在研究生的學習中用一周就能基本入門一種特定的編程語言。當然，我們不是大專，也不是職業培養學校。我們雖然注重工程能力，但是並不要求一個學生在某一門程序語言上成為大牛（這是職業培訓的目的。所以即便很多人是職業培訓出來的，編程能力也可能比我們強）。我們的優勢是在於在注重工程培養的同時，我們還有很多理論學習，報考計算機的各種理論，演算法的各種理論。。。這些理論的學習是給在研究生期間做理論研究做初步准備的。 所以，我認為 一個軟體領域的科研人員，在本科階段應該是一個優秀的程序編寫員。本科的偏工程背景，不應該認為和做理論研究是不相關的。

J. 求圖的最短路徑 c語言

prim演算法或者kruskal演算法啊