【洛谷P3366】【模板】最小生成树 解题报告

这道模板题非常简单，给定一个无向图的各条边以及权值，求最小生成树。可以采用$Prim$算法或者$Kruskal$算法。我用的是$Kruskal$，因为写起来简单（
基本思路如下：

• 先读入点数$n$和边数$m$，然后用一个结构体数组存放每一条边及其权值，用一个$int$变量$ans$存放该最小生成树各边的长度之和。
• 对该结构体使用$C++$自带的$STL$库中的$sort()$函数，对其进行权值的从小到大的排序。
• 然后，从权值最小的边开始遍历所有的边，若该边连接的两个顶点不在一个集合内，则使用并查集进行合并，并在$ans$中加上该边的权值。
• 最后，再对所有点进行一次遍历，判断是否都在一个集合内以确定该图是否连通。若不连通，输出orz；若连通，则输出$ans$。

以下是100pts的代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int MAXN = 5007;//最大点数
const int MAXM = 200007;//最大边数
int n, m;
int f[MAXN];//并查集
struct Node {int x, y, z;
}Arc[MAXM];//边集数组inline int Find(int x) {//并查集寻根&路径压缩return x == f[x] ? x : f[x] = Find(f[x]);
}inline void Merge(int x, int y) {//并查集的合并操作int rx = Find(x), ry = Find(y);if (rx == ry)return;else f[ry] = rx;return;
}inline bool cmp(Node u, Node v) {//结构体排序规则return u.z < v.z;
}inline bool Judge() {//判断所有点是否处于同一集合int Root = Find(1);for (int i = 2; i <= n; ++i)if (Find(i) != Root)return false;return true;
}int main() {cin >> n >> m;for (int i = 1; i <= n; ++i)f[i] = i;//并查集初始化for (int i = 1; i <= m; ++i) cin >> Arc[i].x >> Arc[i].y >> Arc[i].z;sort(Arc + 1, Arc + 1 + m, cmp);//结构体排序，需要的头文件是#include<algorithm>int ans = 0;//存放最小生成树各边的长度之和，int够用for (int i = 1; i <= m; ++i) {//遍历所有边if (Find(Arc[i].x) != Find(Arc[i].y)) {//若顶点x和顶点y不在同一集合Merge(Arc[i].x, Arc[i].y);//合并ans += Arc[i].z;//加上边的权值}}if (!Judge())cout << "orz" << endl;//若图不连通else cout << ans << endl;return 0;
}

总之就是个非常简单的板子题，适合用来练手。
以上。