84pts求条
查看原帖
84pts求条
1181602
Cute_Furina楼主2024/9/25 20:56
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, ans, memo[5010];
bool vis[5010];
struct edge {
	int u, v, t;
}mp[200010];
bool cmp(edge a, edge b) {
	if(a.t != b.t) return a.t < b.t;
	return a.u < b.u;
}
int find(int a) {
	if(a != memo[a]) memo[a] = find(memo[a]);
	return memo[a];
}
signed main() {
	for(int i = 0; i < 5009;i ++) {
		memo[i] = i;
	}
	cin >> n >> m;
	for(int i = 0;i < m;i ++) {
		cin >> mp[i].u >> mp[i].v >> mp[i].t;
	}
	sort(mp, mp + m, cmp);
	for(int i = 0; i < m;i ++) {
		if(find(mp[i].u) == find(mp[i].v)) {
			continue;
		}
		memo[find(mp[i].u)] = memo[find(mp[i].v)];
		ans += mp[i].t;
		vis[mp[i].u] = 1;
		vis[mp[i].v] = 1;
	}
	for(int i = 1;i <= n;i ++) {
		if(vis[i] == 0) {
			cout << "orz" << endl;
			return 0;
		}
	}
	cout << ans << endl;
	return 0 ;
}
2024/9/25 20:56
加载中...