題目鏈接：http://www.patest.cn/contests/mooc-ds/06-3

題目分析：典型最小生成樹問題，且只需輸出樹各邊的權值之和出來就可以了。博主這里用的是Prim算法。

特別說明：

　　1. 用鄰接矩陣表示圖比較容易。保存路徑長度就可以了。因為強調了數組下標從1開始，因此在輸入完n和m時，先執行一步n++，方便以后為數組申請空間。

　　2. 二維數組的動態申請及初始化，不推薦大家#define一個較大的數，然后直接int a[MAX][MAX]，這樣做是十分不負責的，十分浪費空間。如果不會的同學，可以參見如下方法：

1 // 用鄰接矩陣存儲圖 2 int **data = new int*[n]; 3 for(int i=0; i<n+1; i++) 4 { 5 data[i] = new int[n]; 6 } 7 // 鄰接矩陣初始化 8 for(int i=0; i<n; i++) 9 { 10 for(int j=0; j<n; j++) 11 { 12 data[i][j] = MAXNUM; 13 } 14 }

　　3. 求“尚未收集”的dist值最小的函數，參數是dist，collected標記是否被收集，及數組的長度n。注意數組下標從1開始：

1 int minDist(int dist[], bool collected[], int n) 2 { 3 int mindist = MAXNUM; 4 int icount = NOTEXIST; 5 for(int i=1; i<n ; i++) 6 { 7 if(dist[i] < mindist && collected[i] == false) 8 { 9 icount = i; 10 mindist = dist[i]; 11 } 12 } 13 return icount; 14 }

　　4. 用#define定義無窮大（100000000）和不存在（-1），避免程序中出現魔數，也方便修改。

1 #define MAXNUM 10000000 2 #define NOTEXIST -1

　　5. 可以用fill函數，對一個數組進行快速初始化，避免寫for循環。方法如下：

1 fill(a, a+aLen, 100); // 數組a長度為aLen，用100填滿整個數組

代碼分析：

　　普利姆算法：24~71（其中parent數組不設定也可以，這里并沒有要求表示樹的結構）

　　主函數：72~100（注意輸入圖的數據時，注意是圖是無向圖，也就是雙向圖）

1 #include <iostream> 2 #include <stack> 3 4 #define MAXNUM 10000000 5 #define NOTEXIST -1 6 7 using namespace std; 8 9 int minDist(int dist[], bool collected[], int n) 10 { 11 int mindist = MAXNUM; 12 int icount = NOTEXIST; 13 for(int i=1; i<n ; i++) 14 { 15 if(dist[i] < mindist && collected[i] == false) 16 { 17 icount = i; 18 mindist = dist[i]; 19 } 20 } 21 return icount; 22 } 23 24 int Prim(int *data[], int n, int m) 25 { 26 // 集合: 用來存儲收集到的結點 27 stack<int> MST; 28 MST.push(0); 29 // dist: 記錄長度 30 int *dist = new int[n]; 31 fill(dist, dist+n, MAXNUM); 32 dist[1] = 0; 33 // collected: 標記是否被訪問 34 bool *collected = new bool[n]; 35 fill(collected, collected+n, false); 36 // parent: 記錄樹的結構 37 int *parent = new int[n]; 38 fill(parent, parent+n, NOTEXIST); 39 // output: 最終結果 40 int output = 0; 41 while (1) 42 { 43 int V = minDist(dist, collected, n); 44 if (V == NOTEXIST) 45 break; 46 MST.push(V); 47 output += dist[V]; 48 dist[V] = 0; 49 collected[V] = true; 50 for(int W=1; W<n; W++) 51 { 52 if(data[V][W] != MAXNUM // 如果W是V的鄰接點 53 && collected[W] == false // 如果W沒有被訪問 54 && data[V][W] < dist[W]) 55 { 56 dist[W] = data[V][W]; 57 parent[W] = V; 58 } 59 } 60 } 61 if(MST.size() != n) 62 return NOTEXIST; 63 else 64 return output; 65 } 66 /* 67 dist[V] = E(s,V)或 正無窮 68 parent[s] = -1（代表根結點） 69 T = O( |V|2 ) 70 */ 71 72 int main() 73 { 74 int n, m; 75 cin >> n >> m; 76 n++; 77 // 用鄰接矩陣存儲圖 78 int **data = new int*[n]; 79 for(int i=0; i<n+1; i++) 80 { 81 data[i] = new int[n]; 82 } 83 // 鄰接矩陣初始化 84 for(int i=0; i<n; i++) 85 { 86 for(int j=0; j<n; j++) 87 { 88 data[i][j] = MAXNUM; 89 } 90 } 91 for(int i=0; i<m; i++) 92 { 93 int a, b, c; 94 cin >> a >> b >> c; 95 data[a][b] = c; 96 data[b][a] = c; 97 } 98 cout << Prim(data, n, m) << endl; 99 return 0; 100 }

AC成果：

?

轉載于:https://www.cnblogs.com/clevercong/p/4215966.html

總結

以上是生活随笔為你收集整理的中国大学MOOC-数据结构基础习题集、06-3、公路村村通的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。