Gooooogle • 1年前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n, m, i, j, u, v, total;
struct edge {
int start, to;
long long val;
} bian[2000005];
int f[100000];
long long ans;
int find(int x) { //并查集部分
if (f[x] == x)
return x;
else {
f[x] = find(f[x]);
return f[x];
}
}
bool cmp(edge a, edge b) { //结构体快排时用到的
return a.val < b.val;
}
inline void kruskal() { //最小生成树
for (int i = 1; i <= m; i++) {
u = find(bian[i].start);
v = find(bian[i].to);
if (u == v)
continue;//判断在不在同一个并查集里面,在就下一个循环
ans += bian[i].val; //不在,就加上
f[u] = v; //连接两个并查集
total++;
if (total == n - 1)
break;//当形成了最小生成树后,退出(之后做的也没用了)
}
}
int main() {
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
f[i] = i;
for (i = 1; i <= m; i++) {
scanf("%d%d%d", &bian[i].start, &bian[i].to, &bian[i].val);
}
sort(bian + 1, bian + m + 1, cmp); //快排边长
kruskal();
if (total + 1 == n) {
printf("%d", ans);
} else {
printf("orz");
}
return 0;
}
评论:
请先登录,才能进行评论