Kruskal算法求最小生成树（模板）
撰写于 2019-11-15
修改于 2019-11-16
分类
ACM
标签
ACM
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
- 把图中的所有边按代价从小到大排序；
- 把图中的n个顶点看成独立的n棵树组成的森林；
- 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
- 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止.
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
int f[maxn];
struct node {
int u;int v;int w;
}edges[maxn];
bool cmp(node a,node b){
return a.w<b.w;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
void join(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)
f[x]=y;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=0;i<m;i++)
{
cin>>edges[i].u>>edges[i].v>>edges[i].w;
}
sort(edges,edges+m,cmp);
int res=0,cnt=0;
for(int i=0;i<m;i++)
{
int a=edges[i].u;int b=edges[i].v;int w=edges[i].w;
a=find(a),b=find(b);
if(a!=b)
{
join(a,b);
res+=w;
cnt++;
}
}
if(cnt < n-1) cout<<"impossible";
else cout<<res;
}
|
