最小生成树

就是贪心加上并查集。

先按边权从小到大排个序，然后草1到m一条一条加边，若这条边相连的两个节点没有被连过，就将这两个点所在的集合合并，这样直到并查集的树的边加到 n - 1 。则最小生成树各边长度之和就是并查集各边长度之和。

因为要记录一条边连接的哪两个节点，所以开一个结构体，里面a, b, c代表a和b之间连接着一条边权为c的边。

上一道例题：https://www.luogu.org/problemnew/show/3366

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 struct Edge{
 7     int x, y;
 8     ll z;
 9     bool operator < (const Edge& other)const{
10         return z < other.z;
11     };
12 }edge[200005];
13 int p[5005];
14 void init()
15 {
16     for(int i = 1; i <= 5000; ++i) p[i] = i;
17     return;
18 }
19 int Find(int x)
20 {
21     return x == p[x] ? x : p[x] = Find(p[x]);
22 }
23 int merge(int a, int b)
24 {
25     int pa = Find(a), pb = Find(b);
26     if(pa == pb) return 0;
27     else
28     {
29         p[pa] = pb;
30         return 1;
31     }
32 }
33 int main()
34 {
35     init();
36     int n, m, cnt = 0;
37     ll mst = 0;
38     scanf("%d%d", &n, &m);
39     for(int i = 1; i <= m; ++i)
40     {
41         scanf("%d%d%lld", &edge[i].x, &edge[i].y, &edge[i]. z);
42     }
43     sort(edge + 1, edge + m + 1);　　//从边权小的边开始加
44     for(int i = 1; i <= m; ++i)
45     {
46         if(merge(edge[i].x, edge[i].y) == 1)
47         {
48             cnt++; mst += edge[i].z;
49         }
50         if(cnt == n - 1)
51         {
52             printf("%lld
", mst);
53             return 0;
54         }
55     }
56     printf("orz
");
57     return 0;
58 }