95598网站服务建设,扬中王老大,手机网站策划书,林和西网站建设目录 1 基础知识2 模板3 工程化 1 基础知识
kruskal算法的关键步骤为#xff1a;
将所有边按照权重从小到大排序。定义集合S#xff0c;表示生成树。枚举每条边(a,b,c)#xff0c;起点a#xff0c;终点b#xff0c;边长c。如果结点a和结点b不连通#xff08;用并查集来… 目录 1 基础知识2 模板3 工程化 1 基础知识
kruskal算法的关键步骤为
将所有边按照权重从小到大排序。定义集合S表示生成树。枚举每条边(a,b,c)起点a终点b边长c。如果结点a和结点b不连通用并查集来维护则将这条边加入到集合S中。
kruskal算法的时间复杂度为O(mlogm)它用来解决稀疏图的最小生成树问题。
2 模板
int n, m; // n是点数m是边数
int p[N]; // 并查集的父节点数组struct Edge // 存储边
{int a, b, w;bool operator (const Edge W)const{return w W.w;}
}edges[M];int find(int x) // 并查集核心操作
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int kruskal()
{sort(edges, edges m);for (int i 1; i n; i ) p[i] i; // 初始化并查集int res 0, cnt 0;for (int i 0; i m; i ){int a edges[i].a, b edges[i].b, w edges[i].w;a find(a), b find(b);if (a ! b) // 如果两个连通块不连通则将这两个连通块合并{p[a] b;res w;cnt ;}}if (cnt n - 1) return INF;return res;
}3 工程化
题目1求最小生成树。
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 2e5 10;
int p[N];
int n, m;struct Edge {int a, b, w;bool operator (const Edge W) const {return w W.w;}
}edges[N];int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}int main() {cin n m;for (int i 0; i m; i) {cin edges[i].a edges[i].b edges[i].w;}//初始化并查集for (int i 1; i n; i) p[i] i;sort(edges, edges m);int res 0, cnt 0;for (int i 0; i m; i) {int a edges[i].a, b edges[i].b, w edges[i].w;a find(a);b find(b);if (a ! b) {p[a] b;res w;cnt ;}}if (cnt n-1) {cout impossible endl;} else {cout res endl;}return 0;
}
