64 lines
1.3 KiB
C++
64 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
// 并查集（路径压缩 + 按 rank/size 合并）
|
|
struct DSU {
|
|
vector<int> fa, siz;
|
|
|
|
DSU(int n): fa(n), siz(n,1) {
|
|
iota(fa.begin(), fa.end(), 0);
|
|
}
|
|
|
|
int find(int x) {
|
|
return (fa[x] == x ? x : fa[x] = find(fa[x]));
|
|
}
|
|
|
|
bool merge(int x, int y) {
|
|
x = find(x);
|
|
y = find(y);
|
|
if (x == y) return false;
|
|
if (siz[x] < siz[y]) swap(x, y);
|
|
fa[y] = x;
|
|
siz[x] += siz[y];
|
|
return true;
|
|
}
|
|
};
|
|
|
|
struct Edge {
|
|
int u, v, w;
|
|
};
|
|
|
|
int main() {
|
|
int n, m;
|
|
cin >> n >> m;
|
|
vector<Edge> edges(m);
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
cin >> edges[i].u >> edges[i].v >> edges[i].w;
|
|
}
|
|
|
|
// 按边权排序（从小到大）
|
|
sort(edges.begin(), edges.end(), [](auto &a, auto &b) {
|
|
return a.w < b.w;
|
|
});
|
|
|
|
DSU dsu(n);
|
|
|
|
long long mst_cost = 0;
|
|
int cnt = 0; // 记录加入 MST 的边数
|
|
|
|
for (auto &e : edges) {
|
|
if (dsu.merge(e.u, e.v)) { // 若这条边不成环，则加入 MST
|
|
mst_cost += e.w;
|
|
cnt++;
|
|
}
|
|
}
|
|
|
|
if (cnt < n - 1) {
|
|
// 图不连通
|
|
cout << -1 << endl;
|
|
} else {
|
|
cout << mst_cost << endl;
|
|
}
|
|
}
|
|
|