题目大意：
给你n个点（n<=100），然后，让你找到一棵生成树，使得 最大值-最小值的边权尽可能的小的生成树。
解题思路：
还是按照最小生成树的思路，一开始对所有的边按照权值大小，从小到大排序。然后，对于一个区间[L,R]，我们每次枚举的时候，如果这个[L,R]使得所有的n个点都联通了，那么定义他们的苗条度为：
最大值-最小值。这个苗条度肯定是<=cost[r]-cost[l].那么，我们就依次枚举这个l，每次都以[l,m]区间内的边建立最小生成树， 如果不能满足n个点的联通，那么就返回-1.其他时候，就返回max-min的值，指导找到找到那个最小的 最大值-最小值 即可。
代码：
# include<cstdio>
# include<iostream>
# include<vector>
# include<algorithm>
using namespace std;
# define MAX 123
# define inf 99999999
int n,m;
struct Edge
{
int u,v,cost;
bool operator < ( const Edge & a)const
{
return cost > a.cost;
}
};
int f[MAX];
vector<Edge>edge;
void init()
{
for ( int i = 0;i<= n;i++ )
f[i] = i;
}
int getf ( int x )
{
if ( f[x]==x )
return x;
else
{
int t = getf(f[x]);
f[x] = t;
return f[x];
}
}
int same ( int x,int y )
{
return getf(x)==getf(y);
}
int kruskal ( int x )
{
init();
int cnt = 0;
int _min = inf, _max = -1;
for ( int i = x;i < m;i++ )
{
Edge e = edge[i];
int u = edge[i].u;
int v = edge[i].v;
int uu = getf(u);
int vv = getf(v);
if ( uu!=vv )
{
f[uu] = vv;
cnt++;
_min = min(_min,e.cost);
_max = max(_max,e.cost);
}
}
if ( cnt==n-1 )
return _max-_min;
else
return -1;
}
int main(void)
{
while ( scanf("%d%d",&n,&m)!=EOF )
{
if(n==0&&m==0)
break;
edge.clear();
for ( int i = 0;i < m;i++ )
{
int a,b,c; scanf("%d%d%d",&a,&b,&c);
edge.push_back((Edge){a,b,c});
}
sort(edge.begin(),edge.end());
int ans = inf;
for ( int i = 0;i < m;i++ )
{
int tmp = kruskal(i);
if ( tmp==-1 )
break;
ans = min(ans,tmp);
}
if ( ans==inf )
puts("-1");
else
printf("%d\n",ans);
}
return 0;
}
11.2.2 例题 11-2 UVA 1395 Slim Span （最大值-最小值尽可能小的生成树）
原文：http://www.cnblogs.com/lushichuanshuo/p/4856327.html