hdu1598 find the most comfortable road （枚举+并查集）

暴力做法枚举最小的边与最大的边
把价值在两条边权之间的边全部加入进去
然后判断一下 S 与 T 之间是否连通就行了
并查集判断加边的时候 merge 就行了

正解枚举完最小边后从小到大枚举最大边然后并查集此时就可以依次加边了
等到枚举下一条最小边时再把并查集的 f 重新清空就行了

贪心的kruskal最小生成树算法思路，把路径按照从小到大排序，然后从小到大依次枚举“最小速度”，
再寻找目标起点到目标终点的路径中的“最大速度”，为了使得它们的差更小，就要使得“最大速度”尽量的小。
那么为了让Start和End有路径，只需要按照kruskal算法从"最小路径"开始构造生成树，一旦发现Start和End有连接了，
那么就表示已经构成满足条件的那个路径。由于路径已经排序好，那么此时所枚举“起点”和“满足条件之点”之差便是最大速度
与最小速度之差。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream> 
 8 #include <iomanip> 
 9 using namespace std ; 
10 
11 const int maxn = 211,maxm = 1011,inf = 1e9 ; 
12 struct node{
13     int from,to,val ; 
14 }e[maxm] ; 
15 int n,m,Q,S,T,mi,k ;
16 int f[maxn] ;  
17 bool flag ; 
18 
19 inline bool cmp(node a,node b) 
20 {
21     return a.val < b.val ; 
22 }
23 
24 inline void pre() 
25 {
26     for(int i=1;i<=n;i++)
27         f[ i ] = i ;  
28 }
29 
30 inline int getfather(int x) 
31 { 
32     if(f[x]==x) return x ; 
33     f[ x ] = getfather(f[ x ]) ; 
34     return f[ x ] ;  
35 }
36 
37 inline void Union(int x,int y) 
38 {
39     int xx = getfather(x) ; 
40     int yy = getfather(y) ; 
41     if(xx!=yy) f[xx] = yy ;  
42 }
43 
44 int main() 
45 {
46     int x,y ; 
47     while(~scanf("%d%d",&n,&m)) 
48     {
49         for(int i=1;i<=m;i++) 
50             scanf("%d%d%d",&e[ i ].from,&e[ i ].to,&e[ i ].val) ;  
51         sort(e+1,e+m+1,cmp) ; 
52         scanf("%d",&Q) ; 
53         while(Q--) 
54         {
55             scanf("%d%d",&S,&T) ; 
56             mi = inf ; 
57             for(int i=1;i<=m;i++) 
58             {
59                 pre() ; 
60                 flag = 0 ;  
61                 for(int j=i;j<=m;j++) 
62                 {
63                     Union(e[ j ].from,e[ j ].to) ; 
64                     x = getfather(S) ; 
65                     y = getfather(T) ; 
66                     if(x==y) 
67                     {
68                         k = j ; 
69                         flag = 1 ; 
70                         break ; 
71                     }
72                 }
73                 if(flag) mi = min(mi,e[ k ].val - e[ i ].val ) ; 
74             }
75             if(mi==inf) 
76                 printf("-1
") ; 
77             else 
78                 printf("%d
",mi) ; 
79         }
80     }
81     return 0 ; 
82 }