题意：给一个图，找一棵生成树，其满足：最大权-最小权=最小。简单图，不一定连通，权值可能全相同。
思路：点数量不大。根据kruscal每次挑选的是最小权值的边，那么苗条度一定也是最小。但是生成树有多棵，苗条度自然也有多个，穷举下所有生成树，就知道了结果了。根据“只要起始边不同，生成树必定不同”来穷举起始边。
又发现一可能的坑！！我以为LONG_MAX就是int的正最大值，也就是2147483647=2^31-1，在我的机器上也许如此，在OJ上不一定了，用LONG_MAX转int会不同，得注意。
#include <bits/stdc++.h>
using namespace std;
const int N=+;
const int INF=0x7f7f7f7f;
int g[N][N];
int n, m;
int pre[N];
vector< pair<int,int> > vect;
inline int cmp(pair<int,int> a,pair<int,int> b)
{
return g[a.first][a.second]<g[b.first][b.second]? true: false;
} int find(int x)
{
return pre[x]==x? x: pre[x]=find(pre[x]);
}
void joint(int a,int b)
{
a=find(a);
b=find(b);
if(a!=b) pre[a]=b;
} int kruscal(int i)
{
int q=vect[i].first;
int p=vect[i].second;
int cnt=;
for(int i=; i<=n; i++) pre[i]=i; for(int j=i; j<m; j++)
{
int a=vect[j].first;
int b=vect[j].second;
if(find(a)!=find(b))
{
cnt++;
if(cnt==n-) return g[a][b]-g[q][p];
joint(a,b);
}
}
return INF;
} int cal()
{
if(m<n- || kruscal()==INF) return -;//不连通 sort(vect.begin(), vect.end(), cmp);
int ans=INF;
for(int i=; i<m; i++)
{
int q=kruscal(i);
if(q==INF) continue;
ans=min(ans,q);
}
return ans;
} int main()
{
//freopen("input.txt", "r", stdin);
int a, b, w;
while(scanf("%d%d",&n,&m), n+m )
{
memset(g,,sizeof(g));
vect.clear();
for(int i=; i<m; i++)
{
scanf("%d%d%d",&a,&b,&w);
g[a][b]=g[b][a]=w;
vect.push_back(make_pair(b,a));
}
cout<<cal()<<endl;
}
return ;
}
AC代码