题意：求最大边与最小边差值最小的生成树。n<=100,m<=n*(n-1)/2，没有重边和自环。
题解：
m^2的做法就不说了。
时间复杂度O(n*m)的做法：
按边排序，枚举当前最大的边。
那也就是说，把边排序之后从小到大编号，要在[1,r]这段区间内生成一棵最大边与最小边差值最小的生成树。
那每次生成肯定不行（这就是暴力m^2做法。。），我们考虑继承。
假设[1,r-1]这段区间内的苗条树已经生成，那我们只需要把当前第r条边加进去。
加进去分两种情况：
x和y还没有联通：直接加边
x和y已经联通：这样树上就形成了一个环，我们把环上最小的边删除，那就是当前的苗条树。
我维护一个fa[x]表示x节点的fa是谁，dis[x]表示x节点到fa节点的距离。
找环：
先不把那条边加进去，在x，y暴力不断fa上跳找出lca。x->lca->y->x就是那个环。
一开始lca那里错了。。
暴力找lca：
int find_lca(int x,int y)
{
memset(inx,,sizeof(inx));
memset(iny,,sizeof(iny));
int t=,k=;
while(x) t++,inx[x]=t,x=fa[x];
while(y) k++,iny[y]=k,y=fa[y];
int z=;
for(int i=;i<=n;i++)
{
if(inx[i] && iny[i])
{
if(z==) z=i;
else if(inx[i]<inx[z] || iny[i]<iny[z]) z=i;
}
}
return z;
}
删边：
这道题涉及删边丫。。又要n*m做出来。。
fa[]其实就是一条有向边，其实我们只需要修改fa[]和dis[]就可以了。
我就t0表示那个fa[id]所代表的有向边是要删除的 是在x还是y。
具体看代码把。。注意暴栈（我也不知道为什么），就改成了数组+while。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N=,M=*,INF=(int)1e9;
struct node{
int x,y,d,next,bk;
}a[M];
int n,m,t0,t1,id,f[N],fa[N],dis[N],inx[N],iny[N],c[N],p[N]; bool cmp(node x,node y){return x.d<y.d;}
int maxx(int x,int y){return x>y ? x:y;}
int minn(int x,int y){return x<y ? x:y;} int findfa(int x)
{
if(f[x]==x) return f[x];
return findfa(f[x]);
} int find_lca(int x,int y)
{
memset(inx,,sizeof(inx));
memset(iny,,sizeof(iny));
int t=,k=;
while(x) t++,inx[x]=t,x=fa[x];
while(y) k++,iny[y]=k,y=fa[y];
int z=;
for(int i=;i<=n;i++)
{
if(inx[i] && iny[i])
{
if(z==) z=i;
else if(inx[i]<inx[z] || iny[i]<iny[z]) z=i;
}
}
return z;
} void find_min(int x,int y,int z)
{
int mn=INF,xx=x,yy=y;
while(x!=z)
{
if(dis[x]<mn) mn=dis[x],id=x,t0=xx,t1=yy;
x=fa[x];
}
while(y!=z)
{
if(dis[y]<mn) mn=dis[y],id=y,t0=yy,t1=xx;
y=fa[y];
}
} void change(int x,int pre)
{
int pl=;
c[++pl]=x;p[pl]=pre;
while(x && x!=id)
{
c[++pl]=fa[x];p[pl]=x;
x=fa[x];
}
for(int i=pl;i>=;i--)
{
fa[c[i]]=p[i];
dis[c[i]]=dis[p[i]];
}
} int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
while()
{
scanf("%d",&n);
if(!n) return ;
scanf("%d",&m);
memset(fa,,sizeof(fa));
memset(dis,,sizeof(dis));
for(int i=;i<=n;i++) f[i]=i;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
a[i].x++,a[i].y++;
}
sort(a+,a++m,cmp);
int x,y,z,d,mn,cnt=,ans=INF;
for(int i=;i<=m;i++)
{
x=a[i].x,y=a[i].y,d=a[i].d;
if(findfa(x)!=findfa(y))
{
cnt++;
id=;change(x,y);
dis[x]=d;
f[findfa(x)]=findfa(y);
}
else
{
z=find_lca(x,y);
find_min(x,y,z);
change(t0,t1);
dis[t0]=d;
}
if(cnt>=n-)
{
mn=INF;
for(int j=;j<=n;j++)
if(fa[j]) mn=minn(mn,dis[j]);
ans=minn(ans,d-mn);
}
}
printf("%d\n",ans);
}
return ;
}