洛谷日刷2 | Eternal_zttz

洛谷日刷2

P3366 【模板】最小生成树

洛谷传送门

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct Edge{
int u,v,w;
bool operator < (const Edge&a){
return w<a.w;
}
}edge[200005];
int fa[5005],n,m;
int ans,eu,ev,cnt;
int find(int x){
return x==fa[x]? x:find(fa[x]);
}
void kruskal(){
sort(edge,edge+m);
for( int i=0;i<m;i++){
eu=find(edge[i].u);
ev=find(edge[i].v);
if(eu==ev)
continue;
ans+=edge[i].w;
fa[ev]=eu;
if(++cnt==n-1)
break;
}
}
int main(){
scanf("%d %d",&n,&m);
for( int i=1;i<=n;i++)
fa[i]=i;
for( int i=0;i<m;i++)
scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
kruskal();
printf("%d",ans);
return 0;
}

-------------The End-------------