敖丙 • 2个月前
using namespace std;
int fa[N]; int n, m, cnt = 1; long long ans = 0;
struct edge {
int from, to, w;
} e[M];
void init() {
for (int x = 0; x < N; x++)
fa[x] = x;
}
bool cmp(edge a, edge b) {
return a.w < b.w;
}
void addedge(int u, int v, int w) {
e[cnt].from = u;
e[cnt].to = v;
e[cnt].w = w;
cnt++;
}
int find(int x) {
if (fa[x] != x)
return fa[x] = find(fa[x]);
return fa[x];
}
void uni(int x, int y) {
x = find(x);
y = find(y);
if (x != y)
fa[x] = y;
}
void kruskal() {
int k = 0;
sort(e + 1, e + 1 + m, cmp);
for (int x = 1; x <= m; x++) {
if (find(e[x].from) != find(e[x].to)) {
uni(e[x].from, e[x].to);
k++;
ans += e[x].w;
}
if (k == n - 1) {
cout << ans;
break;
}
}
if (k != n - 1) {
cout << "orz";
}
}
int main() {
init();
cin >> n >> m;
for (int x = 1; x <= m; x++) {
int u, v, w;
cin >> u >> v >> w;
addedge(u, v, w);
}
kruskal();
return 0;
}
评论:
请先登录,才能进行评论