题意：
一棵生成树的苗条度被定义为最长边与最小边的差。
给出一个图，求其中生成树的最小苗条度。
思路：
最开始想用二分，始终想不到二分终止的条件，所以尝试暴力枚举最小边的长度，然后就AC了。
粗略估计最大规模为1e8，用时2873ms，卡着时间过。
一个不明显的优化是枚举输入的每一条边。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; const int inf = 0x3f3f3f3f; int mp[][];
bool vis[];
int d[]; int prim(int n,int lim)
{
memset(vis,,sizeof(vis));
memset(d,inf,sizeof(d)); vis[] = ;
d[] = ; int mx = ,mn = inf; for (int i = ;i <= n;i++)
{
if (mp[][i] >= lim) d[i] = mp[][i];
} for (int i = ;i < n - ;i++)
{
//printf("2333\n"); int x,dis = inf; for (int j = ;j <= n;j++)
{
if (!vis[j] && d[j] < dis && d[j] >= lim)
{
dis = d[j];
x = j;
}
} if (dis == inf) return -; vis[x] = ; mx = max(mx,dis);
mn = min(mn,dis); for (int j = ;j <= n;j++)
{
if (!vis[j] && mp[x][j] < d[j] && mp[x][j] >= lim)
{
d[j] = mp[x][j];
}
}
} return mx - mn;
} int main()
{
int n,m; while (scanf("%d%d",&n,&m) != EOF)
{
if (n == && m == ) break; memset(mp,inf,sizeof(mp)); int mxl = ,mnl = inf; for (int i = ;i < m;i++)
{
int a,b,c; scanf("%d%d%d",&a,&b,&c); mp[a][b] = mp[b][a] = c; mxl = max(mxl,c);
mnl = min(mnl,c);
} int ans = prim(n,mnl); if (ans == -) printf("-1\n");
else
{
for (int i = mnl;i <= mxl;i++)
{
int tmp = prim(n,i); if (tmp == -) break;
else ans = min(ans,tmp);
} printf("%d\n",ans);
}
} return ;
}