并查集每一次都要初始化一下
by qnqfff @ 2022-08-22 11:52:20
@[qnqfff](/user/304534)
```cpp
for(int i=1;i<=n;i++)
f[i]=i;
```
这里应该算初始化了吧,并且我的第一个输出的答案就错了
by 二叉苹果树 @ 2022-08-22 11:53:41
@[Étoiles_Brillantes](/user/270854) 刚才吃饭去了/kk
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int f[100005];
int find(int x)
{
if (f[x]==x)
return x;
else
{
f[x]=find(f[x]);
return f[x];
}
}
struct edge
{
int u,v,w;
bool operator<(const edge& e) const
{
return w<e.w;
}
}a[200005];
int n,m,Min;
int cnt;
int main()
{
while(1)
{
cin>>n>>m;
if(n==m&&m==0)
break;
Min=0x7fffffff;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
cin>>a[i].u>>a[i].v>>a[i].w;
sort(a+1,a+m+1);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)
f[j]=j;
cnt=0;
for(int j=i;j<=m;j++)
if(find(a[j].u)!=find(a[j].v))
{
f[find(a[j].u)]=find(a[j].v);
cnt++;
if(cnt==n-1)
{
if(a[j].w-a[i].w<Min)
Min=a[j].w-a[i].w;
break;
}
}
}
if(Min==0x7fffffff)
cout<<"-1"<<endl;
else
cout<<Min<<endl;
}
return 0;
}
```
已改完,错误有点多你自己看看罢
by qnqfff @ 2022-08-22 12:35:30
@[qnqfff](/user/304534) 感谢!orz
by 二叉苹果树 @ 2022-08-22 12:39:44