【HAOI2006】【BZOJ1050】旅行comf

problem

solution

codes

//just for test2
#include<iostream>
#include<algorithm>
using namespace std;
const int inf = 0xfffffff;
int n, m, sx, ed, _max=inf, _min=1;
int gcd(int a, int b){ return !b?a:gcd(b,a%b); }
struct Edge{ int u, v, w; }e[5010];
bool cmp(Edge a, Edge b){ return a.w<b.w; }
int fa[510];
void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i; }
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int main(){
    cin>>n>>m;
    for(int i = 1; i <= m; i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    cin>>sx>>ed;
    for(int i = 1; i <= m; i++){
        init(n);
        for(int j = i; j >= 1; j--){
            merge(e[j].u,e[j].v);
            if(find(sx)==find(ed)){
                if(e[i].w*1.0/e[j].w < _max*1.0/_min){
                    _max = e[i].w;
                    _min = e[j].w;
                }
            }
        }
    }
    if(_max==inf && _min==1)cout<<"IMPOSSIBLE\n";
    else{
        int r = gcd(_max, _min);
        _max /= r;  _min /= r;
        if(_min == 1)cout<<_max<<"\n";
        else cout<<_max<<"/"<<_min<<"\n";
    }
    return 0;
}
  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80465593