AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
梦都会空
,
2021-12-06 18:14:33
,
所有人可见
,
阅读 191
//大神推荐的视频链接,一看就懂 https://www.bilibili.com/video/BV1Eb41177d1/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010,M=100010;
int p[M];
int n,m;
struct xy
{
int a,b,w;
}d[N];
bool cmp(xy x,xy y)
{
if(x.w<y.w) return true;
else return false;
}
int find(int x)//加入集合
{
if(p[x]!=x) p[x]=find(p[x]);
else return x;
}
int fun()
{
int res=0,cnt=0;//res记录最小生成树的树边权重之和,cnt记录的是全部加入到树的集合中边的数量(可能有多个集合)
for(int i=0;i<m;i++)
{
int a=d[i].a,b=d[i].b,w=d[i].w;
if(find(a)!=find(b))//不允许出现环
{
p[find(a)]=p[find(b)];//将a,b所在集合放到同一个集合中
cnt++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
res+=w;//加入到集合中的边的权重之和
}
}
if(cnt==n-1) return res;//可以生成最小生成树
else return 0x3f3f3f3f;//树中有n个节点便有n-1条边,没有n-1条边无法生成树
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) p[i]=i;//初始化
for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
d[i]={a,b,w};//加入结构体中
}
sort(d,d+m,cmp);//将边的权重按照大小排序
int t=fun();
if(t==0x3f3f3f3f) puts("impossible");
else cout<<t<<endl;
return 0;
}