社区讨论
蒟蒻求助 大佬请看
P1111修复公路参与者 5已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @lo87a609
- 此快照首次捕获于
- 2023/10/27 13:56 2 年前
- 此快照最后确认于
- 2023/10/27 13:56 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[100005];
struct xx{
int x,y,t;
}f[100005];
void makeSet(int n)
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
}
bool cmp(xx x,xx y)
{
return x.t<y.t;
}
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void unionSet(int x, int y) {
x = find(x);
y = find(y);
fa[x] = y;
return;
}
bool check(int x)
{
int s=find(x);
for(int i=1;i<=n;i++)
{
if(s!=find(fa[i]))
{
return false;
}
}
return true;
}
int main()
{
int n,m;
cin>>n>>m;
makeSet(n);
for(int i=1;i<=m;i++)
{
cin>>f[i].x>>f[i].y>>f[i].t;
// if(f[i].x<f[i].y)
// swap(f[i].x,f[i].y);
}
sort(f+1,f+1+n,cmp);
for(int i=1;i<=m;i++)
{
unionSet(f[i].x,f[i].y);
if(check(f[i].x))
{
cout<<f[i].t;
return 0;
}
}
cout<<"-1";
return 0;
}
P1111
求助
为什么 跑if(check()) 第一层就出来
回复
共 9 条回复,欢迎继续交流。
正在加载回复...