社区讨论
Kruskal WA 八个 求找错
P3366【模板】最小生成树参与者 5已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi5hsvjo
- 此快照首次捕获于
- 2025/11/19 12:18 4 个月前
- 此快照最后确认于
- 2025/11/19 12:18 4 个月前
CPP
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 5000 + 10 ;
const int maxm = 200000 + 10 ;
int father[maxn];
struct point{
int l;
int r;
int w;
}a[maxm];
int cmp(point a,point b)
{
return a.w<b.w;
}
int find(int x)
{
if(father[x]!=x) father[x]=find(father[x]);
return father[x];
}
void unionn(int r1,int r2)
{
if(find(r1)!=find(r2))
father[r2]=r1;
}
int main()
{
int n,m,ans=0,rp=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=m;i++)
{
if(find(a[i].l)!=find(a[i].r))
{
unionn(a[i].l,a[i].r);
ans+=a[i].w;
rp++;
}
if(rp==n-1)
break;
}
printf("%d",ans);
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...