题目链接：http://vjudge.net/problem/41567/origin
本来想着m^2的复杂度撑不住，对于这种擦着边的复杂度就好慌。
首先对所有的边排个序，然后枚举每个可以构成生成树的区间（L，R)，取区间里面构成树的边的权值的最小和最大的差值，求最小值即可。
如果已经构成生成树可以break掉优化下。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = ;
struct edge
{
int u,v,w;
};
edge e[maxn];
int pre[];
int Find(int x)
{
return pre[x]==x?x:pre[x]=Find(pre[x]);
}
bool cmp(edge A,edge B)
{
return A.w<B.w;
}
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF&&(n||m))
{
for(int i=;i<=m;i++)
{
scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
}
sort(e+,e+m+,cmp);
int count1 = ;
int ans = ;
for(int i=;i<=m;i++)
{
for(int k=;k<=n;k++) pre[k] = k;
count1 = ;
int minv = ;
int maxv = ;
for(int j=i;j<=m;j++)
{
int x = Find(e[j].u);
int y = Find(e[j].v);
if(x!=y)
{
count1++;
pre[x] = y;
maxv = max(maxv,e[j].w);
minv = min(minv,e[j].w);
}
if(count1>=n)
{
break;
}
}
if(count1>=n)
{
ans = min(ans,maxv-minv);
}
}
if(ans!=) printf("%d\n",ans);
else printf("-1\n");
}
return ;
}