hdu 1598 (并查集加贪心) 速度与激情

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1598

一道带有贪心思想的并查集

所以说像二分，贪心这类基础的要掌握的很扎实才行。

用结构体数组储存公路编号和速度，然后按照速度从小到大的排序，

然后以每条路为起点枚举(已经排了序，所以可以保证可以取最小的)，再利用并查集判断是否走到

最后比较出最小的差值

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int inf=1000000;
 5 int father[1001];
 6 void give(int x)
 7 {
 8     for (int i=0;i<=x;i++)
 9         father[i]=i;
10 }
11 int find(int x)
12 {
13     while(x!=father[x])
14        x=father[x];
15     return father[x];
16 }
17 typedef struct {
18     int st;
19     int ed;
20     int speed;
21 }point;
22 point yj[1001];
23 bool cmp (const point &a,const point &b){return a.speed<b.speed;}
24 int main()
25 {
26     int n,m,i,j,ans,min,num,start,end;
27     int sx,sy;
28     while (~scanf("%d %d",&n,&m))
29     {
30         for (i=1;i<=m;i++)
31             scanf("%d %d %d",&yj[i].st,&yj[i].ed,&yj[i].speed);
32         sort(yj+1,yj+m+1,cmp);
33         scanf("%d",&num);
34         while (num--)
35         {
36             scanf("%d %d",&start,&end);
37             min=inf;
38             for (i=1;i<=m;i++)
39             {
40                give(n);
41                for (j=i;j<=m;j++)
42                {
43                    sx=find(yj[j].st);
44                    sy=find(yj[j].ed);
45                    if (sx!=sy)
46                       father[sx]=sy;
47                    if (find(start)==find(end))
48                    {
49                        ans=yj[j].speed-yj[i].speed;
50                        if (ans<min)
51                           min=ans;
52                        break;
53                    }
54                }
55             }
56             if (min==inf)
57                printf("-1
");
58             else
59                printf("%d
",min);
60         }
61     }
62     return 0;
63 }