1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 int f[100086];
 7 struct edge
 8 {
 9     int from;
10     int to;
11     int weight;
12 };
13 int n, m;
14 int tot;
15 long long ans;
16 vector<edge>e;
17 int find(int x)//普通的并查集
18 {
19     if (f[x] == x)
20         return x;
21     else
22         return f[x] = find(f[x]);
23 }
24 void merge(int a, int b)
25 {
26     int x = find(a);
27     int y = find(b);
28     if (f[x] != f[y])
29         f[y] = x;
30 }
31 bool cmp(edge a, edge b)
32 {
33     return a.weight < b.weight;
34 }
35 int main()
36 {
37     cin >> n >> m;
38     for (int i = 1; i <= n; i++)
39         f[i] = i;//并查集初始化
40     for (int i = 1; i <= m; i++)
41     {
42         int x, y, z;
43         cin >> x >> y >> z;
44         edge t;
45         t.from = x;
46         t.to = y;
47         t.weight = z;
48         e.push_back(t);
49         t.from = y;
50         t.to = x;
51         e.push_back(t);
52     }
53     sort(e.begin(), e.end(), cmp);
54     for (int i = 0; i < e.size(); i++)
55     {
56         if (find(e[i].from) != find(e[i].to))//若你们俩没连在一起，那就连一下
57         {
58             merge(e[i].from, e[i].to);//合并并查集
59             ans += e[i].weight;
60         }
61     }
62     cout << ans << endl;
63     return 0;
64 }

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 struct edge
 5 {
 6     int from;
 7     int to;
 8     int weight;
 9     int next;
10 }e[500005];
11 const int inf = 20041001;
12 int head[100086];
13 int dis[100086];
14 int vis[100086];
15 int tot;
16 long long ans;
17 int n, m;
18 void add(int x, int y, int z)
19 {
20     tot++;
21     e[tot].to = y;
22     e[tot].from = x;
23     e[tot].next = head[x];
24     e[tot].weight = z;
25     head[x] = tot;
26 }
27 long long prim()
28 {
29     for (int i = 2; i <= n; i++)
30         dis[i] = inf;
31     for (int i = head[1]; i; i = e[i].next)
32         dis[e[i].to] = min(dis[e[i].to], e[i].weight);
33     int now = 1;
34     for (int t = 1; t < n; t++)
35     {
36         int minn = inf;
37         vis[now] = 1;
38         for (int i = 1; i <= n; i++)
39         {
40             if (!vis[i] && minn > dis[i])
41             {
42                 minn = dis[i];
43                 now = i;
44             }
45         }
46         ans += minn;
47         for (int i = head[now]; i; i = e[i].next)
48         {
49             int to = e[i].to;
50             if (dis[to] > e[i].weight && !vis[to])
51                 dis[to] = e[i].weight;
52         }
53     }
54     return ans;
55 }
56 int main()
57 {
58     cin >> n >> m;
59     for (int i = 1; i <= m; i++)
60     {
61         int x, y, z;
62         cin >> x >> y >> z;
63         add(x, y, z);
64         add(y, x, z);
65     }
66     cout << prim() << endl;
67     return 0;
68 }