Kruskal 86pts求调
查看原帖
Kruskal 86pts求调
1005693
pengbonan楼主2024/1/25 20:35
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
struct edge {
    int u, v, w;
    bool operator < (const edge &t) {
        return w < t.w;
    }
} e[N];
int f[N], cnt;
long long ans;
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
int n, m;
bool Kruskal() {
    sort(e, e + m);
    for (int i = 0; i < m; i ++) {
        int x = find(e[i].u);
        int y = find(e[i].v);
        if (x != y) {
            f[x] = y;
            ans += e[i].w;
            cnt ++;
        }
    }
    return cnt == n - 1;
}
int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) f[i] = i;
	for (int i = 1; i <= m; i ++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[i].u = x;
		e[i].v = y;
		e[i].w = z;
	}
	if (!Kruskal()) cout << "orz";
	else cout << ans;
	return 0; 
}
2024/1/25 20:35
加载中...