ACM1598并查集方法

find the most comfortable road

Problem Description

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

Input

输入包括多个测试实例，每个实例包括：
第一行有2个正整数n (1<n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q（Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。

Output

每个寻路要求打印一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达，那么输出-1。

Sample Input

4 4

1 2 2

2 3 4

1 4 1

3 4 2

1 3

1 2

Sample Output

并查集的伟大力量正等着我们去挖掘，这里再一次让我们脑力激荡。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 using namespace std;
  5 const int oo=11111111;
  6 const int N=220;
  7 class Coor
  8 {
  9     public:
 10     int s,e,speed;//代表线的起始点和终点
 11     friend bool operator<(Coor a,Coor b)
 12     {
 13     return (a.speed<b.speed);//从小到大排序，这样利用贪心算法比较节省时间
 14     }
 15 };
 16 class Comfort
 17 {
 18     public:
 19         Comfort(int n,int m)//构造函数
 20         {
 21             num=n;
 22             side=m;
 23             p=new int[n+1];//临时分配数组空间
 24             edge=new Coor[m+1];
 25         }
 26         ~Comfort()
 27         {
 28             delete []p;
 29             delete []edge;
 30         }
 31         
 32         void initp()
 33         {
 34             for(int i=0;i<=num;i++)
 35             p[i]=i;
 36         }
 37         void inputedge()
 38         {
 39             for(int i=0;i<side;i++)
 40             cin>>edge[i].s>>edge[i].e>>edge[i].speed;
 41             sort(edge,edge+side);//排序
 42         }
 43         int find(int x)
 44         {
 45             if(x==p[x])return x;
 46             return p[x]=find(p[x]);//压缩路径
 47         }
 48         void Union(Coor coor)
 49         {
 50             int fa=find(coor.s);
 51             int fb=find(coor.e);
 52             if(fa!=fb)p[fa]=fb;
 53         }
 54         void Dealpart(int q)//以下代码的作用是判断从起点到终点路径想通的最大值和最小值
 55         　//详细解释：首先i从零开始，然后下面的循环J从i 开始，在一轮搜索后，应当找到最大值确定的相通路径，若第一轮找不到必然不相通，下面已经处理这样的问题。
 56 　　　　　//第一轮能够确定最大值后，开始循环直到确定最小值，当起点i不断的向前推进，当推进到起点和终点不连通的时候算是找到了最小值。
 57         {
 58             while(q--)
 59             {
 60                 scanf("%d %d",&start,&end);
 61                 less=oo;
 62                 for(int i=0;i<side;i++)
 63                 {
 64                     initp();
 65                     int temp=oo;
 66                     for(int j=i;j<side;j++)
 67                     {
 68                         Union(edge[j]);//这里每次都连接一个，直到连接到起点终点相通为止，先确定最大值，后确定最小值
 69                         int X=find(start);
 70                         int Y=find(end);
 71                         if(X==Y)
 72                         {
 73                             temp=edge[j].speed-edge[i].speed;
 74                             break;
 75                         }
 76                     }
 77                         if(temp<less)
 78                         less=temp;
 79                         if(less==0)break;//如果less已经为零了就不需要继续循环了，因为没有比他更小的了，节约时间
 80                         if(less==oo)break;//如果在第一轮寻找中都没有找到一个确切的值，那么这两个点是不连通的，所以直接退出循环,节约时间
 81                 }
 82                 if(less==oo)cout<<-1<<endl;
 83                 else cout<<less<<endl;
 84             }
 85         }
 86     private:
 87         int less;
 88         int *p;
 89         int num,side;
 90         Coor *edge;
 91         int start,end;
 92 };
 93 int main()
 94 {
 95     int n,m,Q;
 96     while(cin>>n>>m)
 97     {
 98         Comfort    Object(n,m);
 99         Object.inputedge();
100         cin>>Q;
101         Object.Dealpart(Q);
102     }
103     return 0;
104 }

What I don't dare to say is I can't!