无向图最小生成树（prim算法）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <cstdio>
 5 #include <string>
 6 #include <cstring>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <set>
11 #define INF 0x3f3f3f3f
12 #define INFL 0x3f3f3f3f3f3f3f3f
13 #define zero_(x,y) memset(x , y , sizeof(x))
14 #define zero(x) memset(x , 0 , sizeof(x))
15 #define MAX(x) memset(x , 0x3f ,sizeof(x))
16 using namespace std;
17 #define N 1005
18 typedef long long LL ;
19 int G[N][N];
20 int minn[N];///寻找最小权；
21 bool point[N];
22 
23 int main(){
24     //freopen("in.txt","r",stdin);
25     memset(point, 0, sizeof(point));
26     int n, m, x, y, ans=0;
27     scanf("%d%d", &n, &m);
28     for(int i=1;i<=n;i++){
29         for(int j = 1; j <= n; j++){
30             G[i][j] = INF;
31         }
32     }
33     for(int i = 1; i <= m; i++) {
34         scanf("%d%d", &x, &y);
35         scanf("%d", &G[x][y]);
36         G[y][x] = G[x][y];
37     }
38     point[1] = true;
39     for(int i = 1;i <= n; i++) minn[i] = G[1][i];
40     for(int i = 1 ; i <= n; i++){
41         int k = 0, mi = INF;
42         for(int j = 1; j <= n; j++){
43             if(!point[j] && minn[j] < mi){
44                 mi = minn[j];
45                 k = j;
46             }
47         }
48         ans += minn[k];
49         point[k] = true;
50         for(int s = 1;s <= n; s++){
51             if(!point[s] && G[k][s] < minn[s])///保存了之前没有加入集合的边的权；
52                 minn[s] = G[k][s];
53         }
54     }
55     printf("%d\n", ans);
56     return 0;
57 }