洛谷P3366最小生成树

传送门啦

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define re register
using namespace std;
const int maxn = 5005;
const int maxm = 200005;

inline int read(){
	char ch = getchar();
	int f = 1 , x = 0;
	while(ch > '9' || ch < '0' ){if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ;ch = getchar();}
	return x * f;
}

int n,m,x,y,z;
int head[maxn],tot;
int cnt,ans,fa[maxn];

struct Edge{
	int from,to,val,next;
}edge[maxm << 1];

inline void add(int u , int v, int  w){
	edge[++tot].from = u ;
	edge[tot].to = v;
	edge[tot].val = w;
	edge[tot].next = head[u];
	head[u] = tot;
}

inline void init(){
	for(re int i = 1 ; i <= n ; ++i)
		fa[i] = i ;
}

inline int find(int x){
	if(x != fa[x])  fa[x] = find(fa[x]);
	return fa[x];
}

inline bool cmp(Edge a , Edge b){
	return a.val < b.val ;
}

int main(){
	n = read() ; m = read();
	for(re int i = 1 ; i <= m ; ++i) {
		x = read(); y = read(); z = read();
		add(x , y , z);
		add(y , x , z);
	}
	init();
	sort(edge + 1 , edge + 1 + tot , cmp);
	for(re int i = 1 ; i <= tot ; ++i){
		int f1 = find(edge[i].from) , f2 = find(edge[i].to);
		if(f1 != f2) {
			cnt++;
			fa[f1] = f2;
			ans += edge[i].val ;
		}
		if(cnt == n - 1) break;
	}
	printf("%d
",ans);
	return 0;
}