P3366 【模板】最小生成树

#include<bits/stdc++.h>
#define N 200005
using namespace std;
inline int read(){
    register int x=0,f=1;
	char c=getchar();
    while(c<'0'||c>'9'){
		if(c=='-')
			f=-1;
		c=getchar();
	}
    while(c>='0'&&c<='9')
		x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
struct Edge{
	int u,v,w;
}edge[N];
int fa[5055],n,m,ans,eu,ev,cnt;
inline bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
inline int find(int x){
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
inline void kruskal(){
    sort(edge,edge+m,cmp);
    for(register 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(){
    n=read(),m=read();
    for(register int i=1;i<=n;++i)
        fa[i]=i;
    for(register int i=0;i<m;++i)
        edge[i].u=read(),edge[i].v=read(),edge[i].w=read();
    kruskal();
    printf("%d",ans);
    return 0;
}