数据范围及提示Data Size & Hint
最终答案需要用long long类型来保存
这题就是纯克鲁斯卡尔算法，有些人说是克鲁斯卡尔加上并查集，我认为克鲁斯卡尔的核心就是并查集
先从权值最小的边开始，然后维护整个边集集合，，防止出现环
注意代码中的查找带了路径压缩
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 100005struct Node{int begin;int end;int len;}a[N];int pa[N];bool cmp(Node a, Node b){return a.len < b.len;}int findset(int x){return pa[x] != x ? pa[x] = findset(pa[x]) : x;}int main(){int m, n;scanf("%d%d", &n, &m);int i;for (i = 1; i <= n; i++)pa[i] = i;for (i = 0; i < m; i++)scanf("%d%d%d", &a[i].begin, &a[i].end, &a[i].len);sort(a, a + m, cmp);long long sum = 0;int ans = 0;for (i = 0; i < m && ans < n; i++){int x = findset(a[i].begin);int y = findset(a[i].end);if (x != y){sum += a[i].len;pa[x] = y;ans++;}}printf("%lld\n", sum);return 0;}
生气是拿别人做错的事来惩罚自己
