| C++刷题周记(五) | 您所在的位置：网站首页 › 刷课时代码 › C++刷题周记(五) |
|
目录 最小生成树 基础概念 应用场景 辨析最小生成树与最短路径 Prim算法 概念 代码模板 辨析Prim与Dijkstra 并查集 思路 Kruskal算法 概念 代码模板 两种方法的辨析 最小生成树 基础概念图论中的最小生成树指的是：包含原图的所有节点（假设图的节点数为n，最小生成树的边数则为n-1），且所用边权值最小的一条路径。 ps：图中可能存在重边和自环，边权可能为负数 应用场景要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。 其他不同的表达方式：城市群之间修建公路/铁路，局部区域岛屿联通修桥...... 常用Prim/Kruskal这两种算法解决最小生成树问题。 辨析最小生成树与最短路径最小生成树：把连通的图的所有顶点连起来路径之和最小的问题，即生成树路径总权值之和最小。 最短路：把两点之间路径最短。最短路只需要将连接起点到终点，其路径并不一定经过所有点，即图中可以有孤立点。而最小生成树要连接图中的每一个点，不能有孤立点。 Prim算法 概念Prim算法 : 把所有点到 已连通集合 的距离dis设成∞ ，每次找到距离最小的点，加入到连通集合中，并用该点距离进行松弛操作，更新所有点到集合距离 dis[i]=min(dis[i],g[t][i]) 即：从图中任意找一个起点，每次循环均要找到当前距连通集合最近的点，直到所有点都加入连通集合。 代码模板模板题：Acwing 858 该代码与朴素Dijkstra的板子相似，流程与思想也比较接近 // 稠密图用邻接矩阵 int g[N][N]; // 记录点至连通集合的距离 int dist[N]; // 结点是否在连通集合中 bool state[N]; // 与迪杰算法的区别 D中的松弛操作是更新到起始点的距离 // 而Prim是更新到集合S的距离 int prim(){ memset(dist,0x3f,sizeof dist); int res = 0; // 当i=0时 第一次循环 所取的t点一定为1 dist[1] = 0;// 起点的dist一定为0 从而无需在循环里特判 for(int i = 0; i < n; i++){ int t = -1; //*1 寻找已连通集合之外 距连通集合最近的点t for(int j = 1; j dist[j])){ t = j; } } // *2 状态更新，加入结果 // 当距离为INF，表示图中有不与集合连通的孤立点，此时肯定没有最小生成树 if(dist[t] == INF) return INF; res += dist[t]; state[t] = true; // *3 g[t][j]即为j至 刚加入连通集合中的点t 的距离 根据此进行松弛操作 for(int j = 1; j > n >> m; for(int i = 0; i < m; i++){ int a,b,w; cin >> a >> b >> w; edges[i] = {a,b,w}; } // 点的并查集初始化 for(int i = 1; i |
| CopyRight 2018-2019 实验室设备网 版权所有 |