社区讨论
Kruskal WA 3点
P3366【模板】最小生成树参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi6hbahh
- 此快照首次捕获于
- 2025/11/20 04:52 4 个月前
- 此快照最后确认于
- 2025/11/20 04:52 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
#define MAXM 401000
struct bian
{
int x,y,l;
};
bian a[MAXM];
int f[MAXM],n,m;
bool cmp(bian a,bian b)
{
return a.l<b.l;
}
int zhao(int x)
{
if(x == f[x])
return x;
return f[x] = zhao(f[x]);
}
void he(int x,int y)
{
int fx=zhao(x);
int fy=zhao(y);
f[fy] = fx;
}
void rd()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);
}
for(int i=1;i<=n;i++)
f[i] = i;
}
int main()
{
rd();
sort(a+1,a+m+1,cmp);
int s = 0,ans = 0;
for(int i=1;i<=m;i++)
{
if(zhao(a[i].x)!=zhao(a[i].y))
{
ans += a[i].l;
s++;
he(a[i].x,a[i].y);
}
if(s == n-1)
break;
}
if(s < n-1)
cout<<"orz";
else
cout<<ans<<endl;
return 0;
}
/*
5 5
1 2 1
1 3 1
2 3 2
1 5 5
4 5 3
1 4 6
*/
回复
共 2 条回复,欢迎继续交流。
正在加载回复...