首页 > 代码库 > 【模版】最小生成树Kruskal模版
【模版】最小生成树Kruskal模版
最小生成树简单来说就是在一个有$n$条边的有权无向连通图中选出$n-1$条边，使图连通并且这$n-1$条边的边权和最小。
Kruskal算法是用一种贪心的思想，先将所有的边按边权排序，按边权从小到大顺序枚举边，如果起点和终点不在一个集合，就选这条边，并将起点和终点合并成一个集合；反之则不选此边。集合可以用并查集维护。
（以上内容纯属瞎编，若要系统学习请百度）
下面是模版
//最小生成树(Kruskal)模版 //By LC 2017.2.19整理 #include <cstdio>#include <algorithm>using namespace std;const int M = 200005, N = 5005;struct Node { int u, v, w;}a[M];int t[N];bool cmp(Node x, Node y) { return x.w < y.w;}int Find(int i) { if(t[i] == i) return i; else return t[i] = Find(t[i]);}int main() { int n, m, i, j, ans = 0; scanf("%d%d", &n, &m); for(i = 1; i <= m; i++) scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w); for(i = 1; i <= n; i++) t[i] = i; sort(a+1, a+1+m, cmp); for(i = j = 1; i <= m && j <= n; i++) { int ss = Find(a[i].u), tt = Find(a[i].v); if(ss != tt) { ans += a[i].w; t[ss] = tt; j++; } } printf("%d", ans); return 0;}
【模版】最小生成树Kruskal模版
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。