【模板】最小生成树

kruskal算法基于并查集思想qwq

prim我不会吖QAQ

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define maxn 5050
 5 #define maxm 200020
 6 using namespace std;
 7 int n,m,num = 0,ans = 0;
 8 int f[maxn];
 9 struct edge {
10     int u, v, w;
11 }e[maxm];
12 bool cmp(edge a,edge b) {
13     if(a.w == b.w) return a.u <b.u;
14     return a.w < b.w;
15 }
16 int init(int x) {for(int i = 1; i <= x; i++) f[i] = i;}
17 int find(int x) {
18     if(x != f[x]) f[x] = find(f[x]);
19     return f[x];
20 }
21 void merge(int x,int y) {f[y] = x;}
22 int main() {
23     scanf("%d%d",&n,&m);
24     init(n);
25     for(int i = 1; i <= m; i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
26     sort(e+1,e+m+1,cmp);
27     for(int i = 1; i <= m; i++) {
28         int r1 = find(e[i].u), r2 = find(e[i].v);
29         if(r1 != r2) {
30             merge(r1,r2);
31             ans += e[i].w;
32             num++;
33         }
34         if(num == n-1) {
35             printf("%d",ans);
36             return 0;
37         }
38     }
39     printf("orz");
40     return 0;
41 }

总之岁月漫长，然而值得期待。