NYoj 最舒适的路线

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

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

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <ctype.h>
 7 #include <iomanip>
 8 #include <queue>
 9 #include <stdlib.h>
10 using namespace std;
11 
12 #define INF 0x3fffffff
13 
14 int f[5005];
15 int n,m;
16 
17 struct lu
18 {
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<m;i++)
69             scanf("%d %d %d",&num[i].start,&num[i].end,&num[i].speed);
70         sort(num,num+m,cmp);
71         scanf("%d %d",&a,&b);
72         double rate = INF*1.0;
73         for(i=0;i<m;i++){
74             init(n);
75             for(j=i;j<m;j++){
76                 if(find(num[j].start)!=find(num[j].end))
77                     Union(num[j].start,num[j].end);
78                 if(find(a)==find(b))
79                     break;
80             }
81             if(j==m) break;
82             int v1=num[i].speed,v2=num[j].speed;
83             if(v1*1.0 / v2 < rate){
84                 aa=v1,bb=v2;
85                 rate=v1*1.0 / v2;
86             }
87         }
88         if(rate == INF)
89             printf("IMPOSSIBLE
");
90         else if(aa % bb == 0)
91             printf("%d
",aa/bb);
92         else
93             printf("%d/%d
",aa/ gcd(aa,bb),bb/ gcd(aa,bb));
94     }
95 }