目录
题目描述
输入格式
输出格式
输入输出样例
说明/提示
代码：
无注释版：
有注释版：
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 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"; // 输出最小生成树的总权重}
}
