编辑代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, m;
const int maxn = 2e5 + 5;
const int minn = 5e3 + 5;
struct wide {
	int from, to, dis;
}cj[maxn];
int a[minn],node1,node2,ans,cnt;
inline bool cmp(wide a,wide b){//按边从小到大排序
	return a.dis < b.dis;
}
inline int find(int x) {
	return x == a[x] ? x : a[x] = find(a[x]);//路径压缩
}
inline void kruskal() {
	sort(cj, cj + m, cmp);
	for (register int i = 0; i < m; i++) {
		node1 = find(cj[i].from), node2 = find(cj[i].to);
		if (node1 == node2)continue;//若两个点联通，舍去
		ans += cj[i].dis;
		a[node2] = node1;//将node1连接到node2上
		if (++cnt == n - 1)//边数==点数-1时退出循环
			break;
	}
}
inline int read() {
	register int x = 0; bool falg = 1; char ch = getchar();
	while (ch < '0' or ch>'9') { if (ch == '-')falg = 0; ch = getchar(); }
	while (ch >= '0' and ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	if (falg)return x;
	return ~(x - 1);
}
int main() {
	n = read(),m = read();
	for (register int i = 1; i <= n; i++)//初始化并查集
		a[i] = i;
	for (register int i = 0; i < m; i++) {//建立无向图
		cj[i].from = read(), cj[i].to = read(), cj[i].dis = read();
	}
	kruskal();
	cout << ans<<endl;
	return 0;
}