1.题目描述：点击打开链接
2.解题思路：本题实质上还是利用Kruskal算法来生成MST。首先按照边权值由小到大排序，对于一个连续的边集[L,R]，，如果使得这n个点全部连通，则一定存在一个苗条度不超过w[R]-w[L]的生成树。因此，可以从小到大枚举L，对于每一个L，利用Kruskal算法生成最小生成树后，计算苗条度，用ans取最小的即可。如果枚举结束后ans依然是INF。那么输出-1。这里可以加上一个预处理：如果m<n-1，那么直接输出-1。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 5000+10#define INF 100000000int u[N], v[N], w[N];int r[N], p[N];int n, m;int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}int cmp(const int i, const int j){return w[i] < w[j];}int Kruskal(int L){int ans = -1;int R;for (int i = 1; i <= n; i++)//初始化并查集p[i] = i;for (R = L; R < m; R++){int e = r[R];int x = find(u[e]);int y = find(v[e]);if (x != y){ans = max(ans, w[e] – w[r[L]]);p[x] = y;}}int fa = find(1);for (int i = 1; i <= n; i++)//判断n个点是否都连通if (fa != find(i))return ans=INF;return ans;}int main(){//freopen("test.txt", "r", stdin);while (cin >> n >> m && (n || m)){int ans = INF;for (int i = 0; i < m; i++)scanf("%d%d%d", &u[i], &v[i], &w[i]);for (int i = 0; i < m; i++)r[i] = i;sort(r, r + m, cmp);if (m < n – 1)printf("-1\n");else{for (int i = 0; i < m – n + 2; i++)ans = min(ans, Kruskal(i));if (ans == INF)printf("-1\n");else printf("%d\n", ans);}}return 0;}
他们比任何人都分毫较量，又比任何人都口是心非。他们比任何人都依赖彼此，
