1 // 无向图求最小生成树权值Prim算法 2 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 int maps[505][505]; 8 bool visit[505]; 9 int lowcost[505]; 10 int Prim(int n) 11 { 12 int ans = 0, i, j; 13 memset(visit, false, sizeof(visit)); 14 visit[1] = true; // prim算法从一个点开始,这里选择点1 15 for (i = 2; i <= n; i++) // 从点2开始将到1花费存入lowcost 16 lowcost[i] = maps[1][i]; 17 for (i = 2; i <= n; i++) 18 { 19 // 找出到现在已选集合cost最小的点 20 int min = INF, p; 21 for (j = 2; j <= n; j++) 22 if (!visit[j] && lowcost[j] < min) 23 { 24 min = lowcost[j]; 25 p = j; 26 } 27 if (min == INF) // 如果没点了说明不连通没有最小生成树,返回-1 28 return -1; 29 // 花费加上此最小花费 30 ans += min; 31 //将这个点加入已选集合 32 visit[p] = true; 33 for (j = 1; j <= n; j++) 34 if (!visit[j] && lowcost[j] > maps[p][j]) 35 lowcost[j] = maps[p][j]; 36 } 37 return ans; 38 } 39 int main() 40 { 41 int n, m; 42 cin >> n >> m; 43 memset(maps, INF, sizeof(maps)); 44 for (int i = 1; i <= n; i++) 45 { 46 int u, v, w; 47 cin >> u >> v >> w; 48 maps[u][v] = w; 49 maps[v][u] = w; 50 } 51 cout << Prim(m) << endl; 52 return 0; 53 }