hdu-1598 find the most comfortable road---kruskal+枚举下界

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1598

题目大意：

XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。

解题思路：

对边进行排序，从小到大枚举下界，依次加入每条边，知道恰好目标点连通，那么正好是最大值-最小值。答案取最小值

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1000 + 10;
 4 const int INF = 0x3f3f3f3f;
 5 struct node
 6 {
 7     int u, v, w;
 8     bool operator <(const node & a)const
 9     {
10         return w < a.w;
11     }
12 }a[maxn];
13 int p[maxn];
14 void init()
15 {
16     for(int i = 0; i < maxn; i++)p[i] = i;
17 }
18 int Find(int x)
19 {
20     return x == p[x] ? x : p[x] = Find(p[x]);
21 }
22 void Union(int x, int y)
23 {
24     p[Find(x)] = Find(y);
25 }
26 int main()
27 {
28     int n, m;
29     while(cin >> n >> m)
30     {
31         for(int i = 0; i < m; i++)
32         {
33             cin >> a[i].u >> a[i].v >> a[i].w;
34         }
35         sort(a, a + m);
36         int t, u, v;
37         cin >> t;
38         while(t--)
39         {
40             cin >> u >> v;
41             int ans = INF;
42             for(int start = 0; start < m; start++)
43             {
44                 init();
45                 for(int end = start; end < m; end++)
46                 {
47                     Union(a[end].u, a[end].v);
48                     if(Find(u) == Find(v))
49                     {
50                         ans = min(ans, a[end].w - a[start].w);
51                     }
52                 }
53             }
54             if(ans < INF)cout<<ans<<endl;
55             else cout<<"-1"<<endl;
56         }
57     }
58     return 0;
59 }