社区讨论
90分?(#2wa)
P1111修复公路参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6vhpqu
- 此快照首次捕获于
- 2025/11/20 11:29 4 个月前
- 此快照最后确认于
- 2025/11/20 11:29 4 个月前
CPP
#include<cstdio>
#include<algorithm>
using namespace std;
struct edg{
int from,w,to;
}edge[200001];
int cnt,fa[200001];
bool cmp(edg a,edg b)
{
return a.w<b.w;
}
int gf(int a)
{
if(fa[a]!=a)
return fa[a]=gf(fa[a]);
else
return a;
}
void hb(int a,int b){
int f1,f2;
f1=gf(a);
f2=gf(b);
if(f1!=f2)
fa[f2]=f1;
return;
}
int judge(int a,int b){
int f1,f2;
f1=gf(a);
f2=gf(b);
if(f1==f2)return 1;
return 0;
}
int main()
{
int a,b,c,i,j=0,n,m,ans=0;
scanf("%d%d",&n,&m);
ans=n;
for(i=1;i<=n;i++)
fa[i]=i;
for(i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].from ,&edge[i].to,&edge[i].w);
sort(edge+1,edge+m+1,cmp);
for(i=1;i<=m;i++)
{
if(!judge(edge[i].from,edge[i].to))
{
hb(edge[i].from,edge[i].to);
j++;
}
if(j==n-1)
{
printf("%d",edge[i-1].w);
return 0;
}
}
printf("-1");
return 0;
} ```
回复
共 4 条回复,欢迎继续交流。
正在加载回复...