slipknot @ 2022-07-26 16:29:52
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,sum=0,g=0;
bool book=0;
int f[114514];
struct huh{
int u,v,w;
};
vector<huh> a;
bool cmp(huh a,huh b)
{
return a.w<b.w;
}
int find(int v)
{
if(f[v]==v)
{
return v;
}
else
{
f[v]=find(f[v]);
return v;
}
}
void hebing(int u,int v)
{
int t1,t2;
t1=find(u);
t2=find(v);
if(t1!=t2)
{
f[v]=t1;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
a.push_back(huh{x,y,z});
}
sort(a.begin(),a.end(),cmp);
for(int i=1;i<=n;i++)
{
f[i]=i;
}
for(int i=0;i<m;i++)
{
if(find(a[i].u)!=find(a[i].v))
{
g++;
hebing(a[i].u,a[i].v);
sum+=a[i].w;
}
if(g==n-1)
{
break;
}
}
cout<<sum;
return 0;
}
by letitdown @ 2022-07-26 16:33:44
find函数的else分支里面改成return f[v]
合并函数里面改成f[t2]=t1
by Waaifu_D @ 2022-07-26 16:34:33
@slipknot 您并查集错了,返回v干什么,还有根本没判断图是否连通
by slipknot @ 2022-07-26 16:37:54
@letitdown @waaifu_D 感谢大佬!