21分求助
查看原帖
21分求助
845330
pengziyippp楼主2023/11/11 10:10
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int f[N];
struct node {
	int st, to, val;
}a[N];
bool cmp (node x, node y) {
	return x.val < y.val;
}
int find(int x) {
	if (f[x] == x) return x;
	return f[x] = find(f[x]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
    	f[i] = i;
	}
	for (int i = 1; i <= m; i ++ ) {
		cin >> a[i].st >> a[i].to >> a[i].val;
	}
	sort (a + 1, a + m + 1, cmp);
	int ans = 0, cnt = 0;
	for (int i = 1; i <= m; i ++ ) {
		if (cnt == n - 1) {
			cout << ans;
			return 0;
		}
		int u = a[i].st, v = a[i].to;
		if (u != v) {
			ans += a[i].val;
			f[u] = v;
			cnt ++;	
		}
	}
	cout << "orz";	
}
2023/11/11 10:10
加载中...