find the most comfortable road

  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 }