1050: [HAOI2006]旅行comf

分析

　　考虑如何统计答案，且复杂度较小，直接搜索是不行的。那么考虑先枚举一条较小的边，然后依次加入比它大的点，一旦ST联通了，那么说明当前比值为最新加入的边比枚举的较小的边，用并查集维护，取最小值。

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4  
 5 inline int read() {
 6     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 7     for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
 8 }
 9  
10 const int N = 5005;
11  
12 struct Edge{
13     int u,v,w;
14     bool operator < (const Edge &A) const {
15         return w < A.w;
16     }
17 }e[N];
18 int fa[505];
19 int gcd(int a,int b) {
20     if (b == 0) return a;
21     return gcd(b,a%b);
22 }
23 int find(int x) {
24     if (x == fa[x]) return x;
25     return fa[x] = find(fa[x]);
26 }
27  
28 int main() {
29     int n = read(),m = read();
30     for (int i=1; i<=m; ++i) {
31         e[i].u = read(),e[i].v = read(),e[i].w = read();
32     }
33     int S = read(),T = read();
34     int ans1 = -1,ans2 = -1;
35     double ans = 1e9;
36     sort(e+1,e+m+1);
37      
38     for (int i=1; i<=m; ++i) {
39         for (int j=1; j<=n; ++j) fa[j] = j;
40          
41         for (int j=i; j<=m; ++j) {
42             int u = find(e[j].u),v = find(e[j].v);
43             if (u != v) fa[u] = v;
44              
45             if (find(S) == find(T)) {
46                 double t = (1.0 * e[j].w) / (1.0 * e[i].w);
47                 if (t < ans) {
48                     ans = t;ans1 = e[i].w,ans2 = e[j].w;
49                 }
50                 break;
51             }
52         }
53         if (ans1 == -1 && ans2 == -1) {
54             puts("IMPOSSIBLE");return 0;
55         }
56     }
57     int d = gcd(ans1,ans2);
58     ans2 /= d,ans1 /= d;
59     if (ans1 == 1) cout << ans2;
60     else cout << ans2 << "/" << ans1; //居然写成了 cout << ans2/d << "\" << ans1/d !!!     
61     return 0;
62 }