修复公路

一道Kruskal算法裸题,可以用利用并查集做

Kruskal算法
Kruskal算法是一种用来查找最小生成树的算法,由Joseph Kruskal在1956年发表。
用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。
和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。

先来讲述一下并查集

并查集是描述不相交集合的数据结构,并支持对这些不相交集合进行合并查找操作。
因此并查集主要就是两个操作:
1.合并操作
2.查找操作
代码如下

1
2
3
4
5
6
7
 int find(int x) {
return x==fa[x] ? x: fa[x]=find(fa[x]);
}//查找操作

void join(int x,int y) {
if(find(x)!=find(y)) fa[find(y)]=find(x);
}//合并操作

所以需要如下方案
1、对图的所有边按照权值大小进行排序。
2、将边添加到最小生成树中时,判断是否形成了回路。
排序就不用说了
判断是否形成了回路,正是并查集的强项
只需把合并操作修改为

1
2
3
4
5
6
7
bool join(int x,int y) {
if(find(x)!=find(y)) {
fa[find(y)]=find(x);
return 1;
}
return 0;
}//判断是否形成了回路

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int fa[100005],n,m;
struct weizi {
int x,y,sum;
} a[100005];
int find(int x) {
return x==fa[x] ? x: fa[x]=find(fa[x]);
}
int join(int x,int y) {
if(find(x)!=find(y)) {
fa[find(y)]=find(x);
return 1;
}
return 0;
}
int cmp(weizi a,weizi b) {
return a.sum<b.sum;
}
int main() {
cin>>n>>m;
for(int i=1; i<=m; i++)cin>>a[i].x>>a[i].y>>a[i].sum;
sort(a+1,a+1+m,cmp);
for(int i=1; i<=n; i++)fa[i]=i;
int count=0;
for(int i=1; i<=m; i++) {
if(join(a[i].x,a[i].y)) {
count++;
}
if(count==n-1) {
cout<<count<<' '<<a[i].sum<<endl;
return 0;
}
}
cout<<-1;
return 0;
}

简单来说,Kruskal算法就是利用了贪心原理,把点的权值排序,然后利用并查集判断是否形成回路,由此求解