当前位置: 首页> 房产> 建筑 > 策划书word模板范文_东莞网推广网站建设_媒体发稿网_百度营消 营销推广

策划书word模板范文_东莞网推广网站建设_媒体发稿网_百度营消 营销推广

时间:2025/7/10 18:13:57来源:https://blog.csdn.net/2201_75933169/article/details/146509004 浏览次数:1次
策划书word模板范文_东莞网推广网站建设_媒体发稿网_百度营消 营销推广

目录

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码:

无注释版:

有注释版:


题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz

输入格式

第一行包含两个整数 N,M,表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi​,Yi​,Zi​,表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​。

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz

输入输出样例

输入 

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 

7

说明/提示

数据规模:

对于 20% 的数据,N≤5,M≤20。

对于 40% 的数据,N≤50,M≤2500。

对于 70% 的数据,N≤500,M≤104。

对于 100% 的数据:1≤N≤5000,1≤M≤2×105,1≤Zi​≤104。

样例解释:

所以最小生成树的总边权为 2+2+3=7。

代码:

无注释版:

#include<bits/stdc++.h>
using namespace std;
int F[5001];
int Find(int x){if(x!=F[x]){F[x]=Find(F[x]);}return F[x];
}
struct Edge{int x,y,w;
}E[200000]; 
bool cmp(Edge e1,Edge e2){return e1.w<e2.w; 
}
int main(){int n,m,x,y,res=0,cnt=0;cin>>n>>m;for(int i=0;i<m;i++){cin>>E[i].x>>E[i].y>>E[i].w;}for(int i=1;i<=n;i++){F[i]=i;}sort(E,E+m,cmp);for(int i=0;i<m;i++){x=Find(E[i].x);y=Find(E[i].y);if(x==y){continue;}F[y]=x;res+=E[i].w;cnt++;if(cnt==n-1){break;} }if(cnt<n-1){cout<<"orz\n";}else cout<<res<<"\n";
} 

有注释版: 

#include<bits/stdc++.h>  // 引入所有标准库头文件,适用于竞赛和快速编写代码
using namespace std;int F[5001];  // 定义一个数组 F,用于存储并查集的父节点,F[i] 表示节点 i 的父节点
// 定义并查集的查找函数,用于找到节点 x 的根节点,并进行路径压缩
int Find(int x) {if (x != F[x]) {  // 如果 x 的父节点不是 x 本身F[x] = Find(F[x]);  // 递归查找 x 的父节点,并将路径压缩}return F[x];  // 返回 x 的根节点
}// 定义边的结构体,包含两个节点 x、y 和边的权重 w
struct Edge {int x, y, w;
} E[200000];  // 定义一个数组 E,存储最多 200000 条边// 定义边的比较函数,用于按边的权重从小到大排序
bool cmp(Edge e1, Edge e2) {return e1.w < e2.w;  // 如果 e1 的权重小于 e2,则返回 true,表示 e1 应排在 e2 前面
}int main() {int n, m, x, y, res = 0, cnt = 0;// 读取图的节点数 n 和边的数量 mcin >> n >> m;// 读取 m 条边的信息for (int i = 0; i < m; i++) {cin >> E[i].x >> E[i].y >> E[i].w;  // 输入每条边的两个端点 x, y 和权重 w}// 初始化并查集的父节点数组,F[i] 表示节点 i 的父节点,初始化为自己for (int i = 1; i <= n; i++) {F[i] = i;  // 每个节点的父节点初始化为它自己}// 按照边的权重从小到大排序sort(E, E + m, cmp);  // 使用 C++ 标准库中的 sort 函数进行排序,按照边的权重升序排序// 遍历所有的边,使用 Kruskal 算法构建最小生成树for (int i = 0; i < m; i++) {x = Find(E[i].x);  // 查找边的第一个节点的根节点y = Find(E[i].y);  // 查找边的第二个节点的根节点// 如果两个节点的根节点相同,说明这条边会形成环,跳过这条边if (x == y) {continue;}// 如果两个节点的根节点不同,说明这条边可以加入最小生成树F[y] = x;  // 将第二个节点的根节点指向第一个节点的根节点,合并两个集合res += E[i].w;  // 累加这条边的权重到结果中cnt++;  // 已加入最小生成树的边数加 1// 如果已加入的边数等于 n-1,说明已经构造出最小生成树if (cnt == n - 1) {break;  // 结束循环}}// 如果已加入的边数不等于 n-1,说明图不连通,无法构成最小生成树if (cnt < n - 1) {cout << "orz\n";  // 输出 "orz",表示图不连通} else {cout << res << "\n";  // 输出最小生成树的总权重}
}

关键字:策划书word模板范文_东莞网推广网站建设_媒体发稿网_百度营消 营销推广

版权声明:

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

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

责任编辑: