当前位置: 首页> 财经> 产业 > 2023年央选职位表_不良网站代码怎么查_百度实时热点排行榜_最新热点新闻

2023年央选职位表_不良网站代码怎么查_百度实时热点排行榜_最新热点新闻

时间:2025/7/10 4:54:24来源:https://blog.csdn.net/buaichifanqie/article/details/142746101 浏览次数:0次
2023年央选职位表_不良网站代码怎么查_百度实时热点排行榜_最新热点新闻

最小生成树

在一个无向图中求一棵树(n-1条边,无环,连通所有点)而且这棵树的边的权和最小

prim(普利姆)算法

prim算法有叫加点法,我们先标定一个点,然后寻找与这个点相连的边的权值最小的点,不断重复此操作,直到所有的点都被连通,我们看下图
在这里插入图片描述
我们以洛谷P3366这道题为例来具体写一下代码

代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>  // 用于memset
using namespace std;const int N = 5010;    // 最大的点数
const int INF = 0x3f3f3f3f;    // 无穷大,表示两个点之间没有直接边
int n;      // n 表示点数
int mp[N][N];        // 邻接矩阵,存储所有边的权重
int dist[N];         // 存储其他点到当前最小生成树的最短距离
bool st[N];          // 用于标记每个点是否已经在生成树中// 初始化函数,将邻接矩阵和其他辅助数组进行初始化
void init() {// 将邻接矩阵所有值设为无穷大INF,表示初始时没有任何边for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {mp[i][j] = INF;}}// 其他辅助数组清空memset(dist, 0x3f, sizeof dist);   // 将 dist 初始化为INFmemset(st, 0, sizeof st);          // 将 st 数组全置为 false(初始时没有点在最小生成树中)
}// Prim算法,计算最小生成树的权重总和
// 如果图不连通,返回 "orz"
int prim() {dist[1] = 0;  // 从第 1 个点开始,初始时距离设为0int res = 0;  // 存储最小生成树的总权重// 遍历 n 次,每次找一个点加入生成树for (int i = 0; i < n; i++) {int t = -1;  // t 用来存储当前距离生成树最近的点// 在所有未加入生成树的点中,找到距离最近的点 tfor (int j = 1; j <= n; j++) {if (!st[j] && (t == -1 || dist[t] > dist[j])) {t = j;}}// 如果除了第一个点以外,某个点的距离为INF,说明图不连通if (i && dist[t] == INF) {cout << "orz" << endl;return 0;}// 如果该点不是第一个点,将其距离加入总权重if (i) {res += dist[t];}st[t] = true;  // 将点 t 标记为已加入生成树// 更新所有其他点到生成树的最短距离for (int j = 1; j <= n; j++) {dist[j] = min(dist[j], mp[t][j]);}}// 返回最小生成树的总权重return res;
}int main() {int m;  // m 表示边数cin >> n >> m;  // 读入点数和边数init();  // 初始化邻接矩阵和其他辅助数组// 读入所有的边for (int i = 1; i <= m; i++) {int u, v, w;  // u, v 表示边的两个端点,w 表示权重cin >> u >> v >> w;// 如果这条边比之前存的边权小,则更新邻接矩阵if (mp[u][v] > w) {mp[u][v] = mp[v][u] = w;}}// 调用 Prim 算法,计算最小生成树的总权重int ans = prim();// 如果图连通,输出最小生成树的权重if (ans) {cout << ans << endl;}return 0;
}

kruskal(克鲁斯卡尔)算法

kruskal算法,又叫加边法,我们把所有点都列出来,然后一次把权值最短的边加上去,要注意加边之后不能形成环,我们看下图
在这里插入图片描述
还是同样的问题我们使用kruskal算法,我们主要是通过并查集来确保不会生成环

代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>  // 用于 std::sort
using namespace std;const int N = 5010;      // 最大点数
const int M = 2e5 + 10;  // 最大边数
const int INF = 0x3f3f3f3f;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];
}// Kruskal 算法求解最小生成树
int kruskal() {// 首先对所有边按照权重排序sort(edges, edges + m);// 初始化并查集,每个点自成一个连通块for (int i = 1; i <= n; i++) p[i] = i;int res = 0, cnt = 0;  // res 保存最小生成树的权重总和,cnt 记录加入生成树的边数// 遍历所有边,按权重从小到大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++;      // 增加计数,表示加入生成树的边数// 如果已经加入了 n - 1 条边,则生成树已经构建完成if (cnt == n - 1) break;}}// 如果连通块的数量小于 n - 1,说明图不连通if (cnt < n - 1) return INF;return res;  // 返回最小生成树的权重总和
}int main() {cin >> n >> m;  // 输入点数和边数// 读入所有边for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;edges[i] = { u, v, w };  // 初始化每一条边}// 调用 Kruskal 算法计算最小生成树int ans = kruskal();// 如果图不连通,输出 "orz",否则输出最小生成树的总权重if (ans == INF) cout << "orz" << endl;else cout << ans << endl;return 0;
}
关键字:2023年央选职位表_不良网站代码怎么查_百度实时热点排行榜_最新热点新闻

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: