#include <bits/stdc++.h>
#define M 100005
#define INF 100000;
using namespace std;
int x,y,i,cent,n,fa[M],que[M],t,ii,ans,a,s,m,j,nn,mins,vis;
struct edge{
int u;
int v;
int w;
bool operator <(
const edge &t)
const
{
return w<
t.w;
}
}es[M];
int findloot(
int kk)
{
while(fa[kk]!=
0) que[++t]=kk,kk=
fa[kk];
while(t>
0) fa[que[t--]]=
kk;
return kk;
}
void lianhe(
int a,
int b)
{
int l=
findloot(a);
int r=
findloot(b);
if(l!=
r)
fa[l]=
r;
}
int main(){
while(~scanf(
"%d%d",&n,&
m))
{
if(n==
0&&m==
0)
break;
ans=INF;vis=
0;cent=
0;
memset(es,0,
sizeof(es));
for(i=
1;i<=m;i++
)
{
scanf("%d%d%d",&x,&y,&
a);
es[cent].u=x,es[cent].v=y,es[cent++].w=
a;
}
sort(es,es+cent-
1);
for(j=
0;j<cent;j++
)
{
memset(fa,0,
sizeof(fa));
mins=
es[j].w;
nn=
n;
for(i=j;i<cent;i++
)
{
if(findloot(es[i].u)!=
findloot(es[i].v))
{ lianhe(es[i].u,es[i].v);
nn--
;
}
if(nn==
1)
{ vis=
1;
ans=min(ans,es[i].w-
mins);
break;
//zhiyi
}
}
}
if(vis==
1)
printf("%d\n",&
ans);
else
cout<<-
1;
}
}
转载于:https://www.cnblogs.com/Lamboofhome/p/11560082.html
相关资源：Benchmarking with DEA, SFA, and R
