bzoj1050

最小生成树

其实这道题是最小生成树的变种，我们发现答案不一定在最小/最大生成树上，最短路算法也不可行，因为我们我们并不是希望最小值尽量的大，最大值尽量的小，这样不一定是最优的，那么我们枚举最小的边，然后将大于他的边依次加入，直到联通，每次求出最大的边和枚举的最小边就是当前答案，更新即可。最大/最小生成树满足使这些点之间的边最大值最小或最小值最大，是一个很好的性质

#include<bits/stdc++.h>

using namespace std;

const int N = ;

struct edge {

    int u, v, w;

    bool friend operator < (edge A, edge B)

    {

        return A.w < B.w;

    }

} e[N];

int n, m, s, t, ans_mx = -, ans_mn = -;

int fa[N];

double ans = 1e9;

int find(int x)

{

    return x == fa[x] ? x : fa[x] = find(fa[x]);

}

int main()

{

//    freopen("comf.in", "r", stdin);

//    freopen("comf.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

    scanf("%d%d", &s, &t);

    sort(e + , e + m + );

    for(int i = ; i <= m; ++i)

    {

        for(int j = ; j <= n; ++j) fa[j] = j;

        fa[e[i].u] = e[i].v;

        int mx = e[i].w, mn = e[i].w;

        for(int j = i + ; j <= m; ++j)

        {

            if(find(s) == find(t)) break;

            int a = find(e[j].u), b = find(e[j].v);

            if(a == b) continue;

            mx = max(mx, e[j].w);

            fa[b] = a;

        }

        if((double)mx / (double)mn < ans && find(s) == find(t))

        {

            ans = (double)mx / (double)mn;

            ans_mx = mx;

            ans_mn = mn;

        }

    }

    if(ans_mx == - && ans_mn == -) puts("IMPOSSIBLE");

    else

    {

        int t = __gcd(ans_mx, ans_mn);

        ans_mx /= t;

        ans_mn /= t;

        printf("%d", ans_mx);

        if(ans_mn != ) printf("/%d\n", ans_mn);

    }

//    fclose(stdin);

//    fclose(stdout);

    return ;

}