题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz
输入输出格式
输入格式：
第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）
接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi
输出格式：
输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz
输入输出样例
输入样例#1：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出样例#1：
7
1.Kruskal算法简介
Kruskal算法一般称作克鲁斯卡尔算法。克鲁斯卡尔算法是一种用来寻找最小生成树的算法。在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。
2.Kruskal算法思想
先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
时间复杂度为为O(e^2), 使用并查集优化后复杂度为 O（eloge），与网中的边数有关，适用于求边稀疏的网的最小生成树。
3.Kruskal算法解题过程
首先我们需要解决一个问题，不能构成回路，这时，我们可以先使用并查集的思想，先把每条边存为独立的根，然后，寻找最短边权时，我们可将已经找过的边合并到集内，防止构成回路，选择其他的次小边。
2259.png
接着就是Kruskal处理核心，我们需要先将边进行排序，这样有利于后面选择最小边。
循环0-n次 且 i < n && nEdge != m - 1，为什么要nEdge != m - 1呢？
这个意思就表达了这个图是不连通的，也同样等价于不存在最小生成树。
接着，我们可以查找这两边的根，如果他们的根节点都不一样，就表示能够增加这个边权，它既是最小的，并且也不会构成回路。然后声明一个记住最小边权变量，最后输出既完成本题目。
下面是具体的代码实现
#include <cstdio>
#include <cstdlib>
#define MAXN 200000 + 10//对于100%的数据
using namespace std;
int par[MAXN], Rank[MAXN];//并查集 rank
typedef struct {
int a, b, price;
}Node;//结构体储存
Node a[MAXN];
int cmp(const void*a, const void *b) {
return ((Node*)a)->price - ((Node*)b)->price;//用于比较边权
}
void Init(int n) {
for (int i = 0; i < n; i++) {
Rank[i] = 0;
par[i] = i;
}
}
int find(int x) {
int root = x;
while (root != par[root]) root = par[root];
while (x != root) {
int t = par[x];
par[x] = root;
x = t;
}
return root;
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (Rank[x] < Rank[y]) {
par[x] = y;
}
else {
par[y] = x;
if (Rank[x] == Rank[y]) Rank[x]++;
}
}
//n为边的数量，m为村庄的数量
int Kruskal(int n, int m) {
int nEdge = 0, res = 0;
//将边按照权值从小到大排序
qsort(a, n, sizeof(a[0]), cmp);
for (int i = 0; i < n && nEdge != m - 1; i++) {
//判断当前这条边的两个端点是否属于同一棵树
if (find(a[i].a) != find(a[i].b)) {
unite(a[i].a, a[i].b);
res += a[i].price;
nEdge++;
}
}
//如果加入边的数量小于m - 1,则表明该无向图不连通,等价于不存在最小生成树
if (nEdge < m - 1) res = -1;
return res;
}
int main() {
int n, m, ans;
scanf("%d%d", &n, &m);
Init(n);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].price);
//将村庄编号变为0~m-1（这个仅仅只是个人习惯，并非必要的）
a[i].a--;
a[i].b--;
}
int rets = Kruskal(m, n);//计算最小生成树
//输出结果
if (rets == -1)
printf("orz");
else printf("%d", rets);
return 0;
}
网友评论