hdu 1811 二分+并查集

 1 #include "stdio.h"  //二分+并查集，，想想道理何在！
 2 #include "stdlib.h"
 3 #include "algorithm"
 4 using namespace std;
 5 #define INF 0x3fffffff
 6 struct node{
 7     int x,y,dis;
 8 }a[1005];
 9 
10 int set[1005];
11 
12 int find(int x){
13     if(set[x]!=x)
14         set[x] = find(set[x]);
15     return set[x];        
16 }
17 
18 int cmp(node u,node v)
19 {
20     return u.dis < v.dis;    
21 }
22 
23 void Union(int x,int y)
24 {        
25     set[find(x)] = find(y);        
26 } 
27 
28 void init(int n) 
29 {
30     int i;
31     for(i=1;i<=n;i++)
32         set[i] = i;    
33 }
34 
35 int main()
36 {
37     int i,j;
38     int n,m,q;
39     while(scanf("%d%d",&n,&m)!=-1)
40     {
41         int x,y,k;
42         for(i=0;i<m;i++)
43         {
44             scanf("%d%d%d",&x,&y,&k);
45             a[i].x = x;
46             a[i].y = y;
47             a[i].dis = k;
48         }
49         sort(a,a+m,cmp);
50         scanf("%d",&q);
51         int min;
52         while(q--)
53         {
54             scanf("%d%d",&x,&y);
55             min = INF;
56             for(i=0;i<m;i++)
57             {
58                 init(n);
59                 for(j=i;j<m;j++)
60                 {
61                     Union(a[j].x,a[j].y);
62                     if(find(x) == find(y))
63                         break;
64                 }
65                 if(j==m) break;
66                 if(min>a[j].dis-a[i].dis)
67                     min = a[j].dis - a[i].dis;
68             }
69             if(min == INF)
70                 printf("-1
");
71             else
72                 printf("%d
",min);
73         }
74     }
75     return 0;
76 }