【BZOJ1050】[HAOI2006]旅行

题面

bzoj
洛谷

题解

先将所有边从小往大排序
枚举钦定一条最小边
再枚举依次枚举最大边，如果两个点联通了就\(break\)统计答案即可
代码

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm>
#include <vector> 
using namespace std;

const int MAX_N = 505; 
const int MAX_M = 5005;
int N, M, S, T, fa[MAX_N]; 
int getf(int x) { return (fa[x] == x) ? x : (fa[x] = getf(fa[x])); }
bool same(int x, int y) { return getf(x) == getf(y); }
void unite(int x, int y) { fa[getf(x)] = getf(y); } 
void clear() { for (int i = 1; i <= N; i++) fa[i] = i; } 
struct Edge { int u, v, w; } e[MAX_M];
bool operator < (const Edge &a, const Edge &b) { return a.w < b.w; } 
double ans = 1e9; 
int ansl, ansr; 
int main () { 
    scanf("%d%d", &N, &M); 
    for (int i = 1; i <= M; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    scanf("%d%d", &S, &T);
    sort(&e[1], &e[M + 1]); 
    for (int i = 1; i <= M; i++) {
        clear(); int j; 
        for (j = i; j <= M; j++) {
            int u = e[j].u, v = e[j].v; 
            if (!same(u, v)) unite(u, v); 
            if (same(S, T)) break; 
        }
        if ((ans > 1.0 * e[j].w / e[i].w) && same(S, T))
            ans = 1.0 * e[j].w / e[i].w, ansl = e[i].w, ansr = e[j].w; 
    } 
    if (ans == 1e9) puts("IMPOSSIBLE");
    else {
        int d = __gcd(ansl, ansr); 
        ansl /= d, ansr /= d; 
        if (ansl == 1) printf("%d\n", ansr);
        else printf("%d/%d\n", ansr, ansl); 
    } 
    return 0; 
} 

【BZOJ1050】[HAOI2006]旅行

原文：https://www.cnblogs.com/heyujun/p/10179074.html