重生成树txt：『最小生成树』最小生成树模板

学习最小生成树前提须知

最小生成树是指一个\(n\)个节点的图，让其变成一个仅有\(n-1\)个边且改变后该图是一张连通图，并且该图最终成为了一棵最小权重生成树（小权值边尽可能留下，大权值边尽可能删除）或最大权重生成树（与前者相反）

算法内容

竞赛需要用到的点

1、最小生成树多用于其他算法的过渡使用，不单独考（xx不要纠结为什么每次都是这一句

2、可用于一种特殊的模板内（即有些边自始至终都不会用到的这种）

最小生成树略讲

最小生成树也是一个很简单的数据结构，它分了三种比较基本的算法Kruskal 算法Prim 算法Boruvka 算法，这三个算法各有各的优缺点，其中Boruvka 算法在这三个算法中可以算是最优的算法，甚至 可以因为Boruvka 算法的特性 卡掉其他两个算法，但这不是我们的重点，先讲一下Kruskal 算法其他两个算法以后再来填坑（xxx 反正Noip之前应该不会了

Kruskal 算法是基于并查集 算法而进行的，很简单的思路就是，对一张图，将所有的边都拆出来，然后对每条边的边权进行排序（从大到小，从小到大看题目需要），然后再将边连回去，连边的时候判断两个点是否被连通了，如果是连通的，那么就将该边扔了再看下一条边，如果没有被连通，那么就将该条边连上，然后用并查集合并即可

那么根据上面信息我们就能够写出代码了

Kruskal 部分代码展现

//#define fre yes#include <cstdio>const int N = 100005;struct Node { int x, y, z;} kru[N];int par[N];void init(int n) { for (int i = 1; i <= n; i++) { par[i] = i; } //起始化}int find(int x) { if(par[x] == x) return par[x]; else return par[x] = find(par[x]);} //并查集 看两点是否在同一个图内bool cmp(Node x, Node y) { return x.z < y.z; //看情况修改 优先级给小边权还是大边权}int main() { ... for (int i = 1; i <= n; i++) { scanf.... kru[i].x = x; kru[i].y = y; ... } std::sort(kru + 1, kru + 1 + n, cmp); for (int i = 1; i <= m; i++) { int x = find(kru[i].x); int y = find(kru[i].y); if(x == y) continue ; //并查集合并操作，看是否在同一个图内 如果在就跳过 不在就合并 par[x] = y; tot++; //这里是判断最后是否连通 } if(tot == p - 1) ... //(p是点的个数)}

若你想将处理之后的图转换到邻接表中怎么办？

const int N = 200005;int head[N << 1], to[N << 1], ver[N << 1], edge[N << 1];int tot;void addedge(int x, int y, int z) { ver[tot] = y; edge[tot] = z; to[tot] = head[x]; head[x] = tot++;}for (int i = 1; i <= m; i++) { int x = find(kru[i].x); int y = find(kru[i].y); if(x == y) continue ; par[x] = y; addedge(kru[i].x, kru[i].y, kru[i].z); addedge(kru[i].y, kru[i].x, kru[i].z);}

这就完成了

完整代码 参考LuoGu P3366

//#define fre yes#include <cstdio>#include <algorithm>const int N = 1000005;struct Node { int x, y, z;} edge[N];int par[N];void init(int n) { for (int i = 0; i <= n; i++) { par[i] = i; }}bool cmp(Node x, Node y) { return x.z < y.z;}int find(int x) { if(x == par[x]) return par[x]; else return par[x] = find(par[x]);}int tot, ans;int main() { static int n, m; scanf("%d %d", &n, &m); init(n); for (int i = 1; i <= m; i++) { int x, y, z; scanf("%d %d %d", &x, &y, &z); edge[i].x = x; edge[i].y = y; edge[i].z = z; } std::sort(edge + 1, edge + 1 + m, cmp); for (int i = 1; i <= m; i++) { int x = find(edge[i].x); int y = find(edge[i].y); if(x == y) continue ; tot++; par[x] = y; ans += edge[i].z; } if(tot < n - 1) puts("orz"); else printf("%d\n", ans); return 0;}

转载于:https://www.cnblogs.com/Nicoppa/p/11475428.html