Hellc

【题目描述】

给定一个无向图，一个起点，一个终点，求一条路径，使得该路径上的最大边权与最小边权的比值最小。

$n \leq 500, m \leq 5000$

【题目链接】

BZOJ 1050 旅行comf [HAOI2006]

【解题思路】

枚举最大边，然后贪心，使最小边尽量大。

即对于枚举的最大边，将比其小的边从大到小依次加入，并查集维护连通性，当起点终点联通时跳出。

【AC代码】

#include <cstdio>
#include <algorithm>
#include <cfloat>
 
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
 
void reduce(int &x, int &y){
    int g = gcd(x, y);
    x /= g, y /= g;
}
 
const int MAXN = 500;
const int MAXM = 5000;
 
int n, m;
 
struct UnionFindSet{
    int f[MAXN];
 
    void init(){
        for(int i = 0; i < n; i++){
            f[i] = i;
        }
    }
 
    int find(int x){
        return f[x] == x ? x : f[x] = find(f[x]);
    }
 
    void merge(int x, int y){
        f[find(x)] = find(y);
    }
 
    bool test(int x, int y){
        return find(x) == find(y);
    }
} ufs;
 
struct Edge{
    int u, v;
    int w;
} edges[MAXM];
 
bool operator<(const Edge &a, const Edge &b){
    return a.w < b.w;
}
 
int s, t;
 
int p, q;
double ans; // ans = \frac p q;
 
inline void updateAns(int x, int y){
    if((double)x / y < ans) p = x, q = y, ans = (double)x / y;
}
 
inline void printAns(){
    if(ans == DBL_MAX){
        puts("IMPOSSIBLE");
    } else{
        reduce(p, q);
        if(q == 1){
            printf("%d\n", p);
        } else{
            printf("%d/%d\n", p, q);
        }
    }
}
 
inline void solve(){
    std::sort(edges, edges + m);
    ans = DBL_MAX;
    for(int i = 0; i < m; i++){
        Edge *x = edges + i;
        ufs.init();
        for(int k = i; k >= 0; k--){
            Edge *e = edges + k;
            ufs.merge(e->u, e->v);
            if(ufs.test(s, t)){
                updateAns(x->w, e->w);
                break;
            }
        }
    }
 
    printAns();
}
 
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++){
        Edge *e = edges + i;
        scanf("%d%d%d", &e->u, &e->v, &e->w), e->u--, e->v--;
    }
    scanf("%d%d", &s, &t), s--, t--;
 
    solve();
 
    return 0;
}

就是这样啦