题目链接：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=711

 

分析：枚举速度最大的边，找出能够从S到达T的最大速度，然后求出它们的比值，与已经求出的比值进行比较，如果比之前的比值小，则更新比值，记录此种情况下的最大速度和最小速度，直到枚举到从S不能到达T，跳出循环。求出最大速度和最小速度的比值即可。如果从S可以到达T，说明S和T属于同一个集合，因此可以利用并查集来判断从S是否可以到达T。

 

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 using namespace std;11 12 #define INF 0x3fffffff13 14 int f[5005];15 int n,m;16 17 struct lu18 {19 int start,end,speed;20 }num[5005];21 22 bool cmp(lu a,lu b)23 {24 return a.speed > b.speed;25 }26 27 int gcd(int a, int b) 28 { 29 while(b != 0) 30 { 31 int r = a % b; 32 a = b; 33 b = r; 34 } 35 return a; 36 } 37 38 void init(int n)39 {40 for(int i=0;i<=n;i++)41 f[i]=i;42 }43 44 int find(int x)45 {46 if(x==f[x])47 return f[x];48 f[x]=find(f[x]);49 return f[x];50 }51 52 void Union(int x,int y)53 {54 int p=find(x);55 int q=find(y);56 if(p > q) 57 f[p] = q; 58 else 59 f[q] = p;60 }61 int main()62 {63 int t;64 int a,b,i,j,aa,bb;65 scanf("%d",&t);66 while(t--){67 scanf("%d %d",&n,&m);68 for(i=0;i