算法刷题【洛谷P3366】最小生成树 - 模板（最小生成树Prim算法和Kruskal算法模板）
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式
第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi,Yi,Zi ，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi 。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
In 1：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3Out 1：
7In 2（评测点 #1）：
5 18 2 4 276 3 3 435 3 4 608 2 4 860 1 2 318 1 3 547 5 4 419 2 5 98 1 5 460 5 3 399 3 5 240 3 2 733 3 3 903 4 2 909 5 2 206 3 4 810 2 1 115 2 3 419Out 2：
729先分析题目：
虽然说是模板题，事实上他还是有一个小坑……也把我卡了好久
最开始是14，后来发现是忘了判断同两个点之间多条路径只存储最小值的问题。
还有一点就是有一些同样点之间有多条路径，应该保存最短的
算法实现：
实话实说，C站最小生成树两种算法详解文章各个都是精品，但是到了代码……未免长了点，注释也不明了。
这篇文章主要针对代码，两个算法的详解也有推荐出文章
Prim算法
算法详解推荐文章：Prim算法_杨氏计算机知识整理-CSDN博客_prim算法
以下可能是最简题解：
#include <bits/stdc++.h>
using namespace std;
int g[5001][5001]; // 存放邻接矩阵
// minn[i]存放未加入最小生成树的点与任意已加入生成树的点路径权值的最小值
int minn[5001];
bool u[5001]; // u[i]=true表示i已加入生成树
int main() {
int n, m;
memset(minn, 0x7f7f7f7f, sizeof(minn)); // 初始化为最大值
memset(g, 0x7f7f7f7f, sizeof(g)); // 初始化为最大值
minn[1] = 0; // 起点赋0值，即默认从起点开始
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
if (z < g[x][y]) g[x][y] = g[y][x] = z; // 无向图输入
}
for (int i = 1; i <= n; i++) {
int k = 0;
for (int j = 1; j <= n; j++) {
if (!u[j] && (minn[j] < minn[k])) k = j;
}
u[k] = true; // k加入最小生成树
if (k == 0) {
// 整个过程一直没有找到路径，但是点还没有加入完，说明图不连通
cout << "orz";
return 0;
}
for (int j = 1; j <= n; j++) {
// 未加入最小生成树且与新加入的k点相邻的点，通过g[k][j]更新minn[j]
if (!u[j] && (g[k][j] < minn[j])) minn[j] = g[k][j];
}
}
int tot = 0;
for (int i = 1; i <= n; i++) {
tot += minn[i];
}
cout << tot;
return 0;
}提交信息：
Kruskal算法
Kruskal算法需要并查集知识，不了解的请看我这篇文章：算法刷题【洛谷P3367】并查集 - 模板_异想之旅的博客-CSDN博客
算法详解推荐文章：最小生成树之Kruskal算法_Enstein_Jun-CSDN博客_kruskal算法
ac代码：
#include <bits/stdc++.h>
using namespace std;
struct edge {
int x, y, v; // 起点、终点和权值
} a[500001];
int edges, tot, k; // 边的数量、生成树中边的权值总和、已加入生成树的边数
int father[5001]; // father[]用于并查集
int check(int x) {
// 并查集查找操作
if (father[x] != x)
return father[x] = check(father[x]);
else
return x;
}
int unionn(int x, int y) {
// 并查集合并操作
x = check(x);
y = check(y);
father[y] = x;
}
bool cmp(edge p, edge q) {
// sort按照边权值从小到大为a排序的自定义比较函数
return p.v < q.v;
}
int main() {
int n, m;
cin >> n >> m;
int t1, t2, t3;
while (m--) {
cin >> t1 >> t2 >> t3;
// 由于随后要进行排序，因此此处无需判断t1,t2两点间是否已存在更短的路径
a[++edges].x = t1;
a[edges].y = t2;
a[edges].v = t3;
}
for (int i = 1; i <= n; i++) father[i] = i; // 初始化并查集
sort(a + 1, a + edges + 1, cmp); // 将所有的边按权值从小到大排序
for (int i = 1; i <= edges; i++) {
if (check(a[i].x) != check(a[i].y)) {
unionn(a[i].x, a[i].y); // 合并两个独立的树
tot += a[i].v; // 总权值加上当前边
k++; // 边数
if (k == n - 1) {
// 最小生成树有n-1条边，因此 k == n - 1 即程序完成
break;
}
}
}
if (k == n - 1)
cout << tot;
else
cout << "orz";
return 0;
}提交信息：
可以看出，无论是空间效率还是时间效率，kruskal算法都是要优于prim算法的
刚刚看评测列表，有一个时间空间非常可以的大神代码……一道模板题都已经上快读快写了，2020年csp入门提高两个一等……大佬牛皮
https://www.luogu.com.cn/record/60442919
