UVA 1395

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4141

题意：

给出一个n（n<=100）结点的图，求苗条度（最大边减最小边的值）尽量小的生成树。

题解：

首先把边按权值从小到大排序。对于一个连续的边集区间[L,R]，枚举L，从L向右枚举R，一旦联通，更新结果，break

代码：

31 int n, m;
32 struct Edge { 
33     int u, v, cost;
34     bool operator<(const Edge& t) {
35         return cost < t.cost;
36     }
37 };
38 Edge E[MAXN*MAXN];
39 int par[MAXN];
40 
41 int find(int x) {
42     return par[x] = par[x] == x ? x : find(par[x]);
43 }
44 
45 void unite(int x, int y) {
46     int a = find(x), b = find(y);
47     if (a != b) par[a] = b;
48 }
49 
50 int main() {
51     ios::sync_with_stdio(false), cin.tie(0);
52     while (cin >> n >> m, n) {
53         rep(i, 0, m) cin >> E[i].u >> E[i].v >> E[i].cost;
54         sort(E, E + m);
55         int ans = INF;
56         rep(i, 0, m) {
57             rep(k, 1, n + 1) par[k] = k;
58             rep(j, i, m) {
59                 unite(E[j].u, E[j].v);
60                 int rt = find(1), fg = 1;
61                 rep(k, 2, n + 1) if (find(k) != rt) {
62                     fg = 0;
63                     break;
64                 }
65                 if (fg) {
66                     ans = min(ans, E[j].cost - E[i].cost);
67                     break;
68                 }
69             }
70         }
71         if (ans == INF) ans = -1;
72         cout << ans << endl;
73     }
74     return 0;
75 }