题目描述

第一行给你个点，条边，每条边都有一个权值。接着给出边的信息。最后给你两个点，问从到的路径中，最长边除以最短边的比值最小是多少？

Solution

观察题目范围，发现点很少，边不是很多，说明我们可以暴力一点。
那么第一步判断是否存在路径从去，从起点图判断两个点之间是否联通，找到并查集这个数据结构。借助并查集可以查询初始条件下，也就是全部边走一遍看我能不能去到，如果这样都不行，说明不存在路径，否则一定存在一条路径走到。这也是唯一输出的条件。
那么接下来我们找到存在一条路，就要满足最大值比最小值最小的这个条件了。一般的最大值最小问题都会往二分这边靠，这里不需要那么复杂，直接沿用上面的方法，我们可以借助并查集，在起始的图中判断两个点是否联通。
那么如果我们枚举边权最小的边，接下来是不是只需要找到使得联通的最大的边是多少即可求得这一条最小边带来的答案。这里就需要类似的算法思想了，如果你懂，那么这个弯路应该不是那么难想到。
这样我们枚举全部的最小边，再去早使得他们联通的最大边，最坏情况就是遍历全部的边。并查集的复杂度因为可以近似看作。那么循环次数就是，就愉快的了。注意我们最后的输出格式。
假设之前答案是，现在来的，如果也就是我们的答案需要更新的时候，那么做等价乘法就是。我们这样做的目的就是为了后面还要输出最简分式，方便输出。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5000 + 7;

struct Node {
    int u, v, w;
    bool operator < (const Node& opt) const {
        return w < opt.w;
    }
}e[N << 1];

int n, m, s, t;
int fa[N];
void init() { rep(i, 1, n) fa[i] = i; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu != fv)    fa[fv] = fu;
}

int up = 3e4 + 7, dw = 0;
void up_ans(int x, int y) {
    if (up * y > x * dw)    up = x, dw = y;
}

void solve() {
    n = read(), m = read();
    init();
    rep(i, 1, m) {
        e[i].u = read(), e[i].v = read(), e[i].w = read();
        merge(e[i].u, e[i].v);
    }
    s = read(), t = read();
    if (find(s) != find(t)) {
        puts("IMPOSSIBLE");
        return;
    }
    sort(e + 1, e + 1 + m);
    for (int i = 1; i < m; ++i) {
        init();
        for (int j = i; j <= m; ++j) { // 注意把 i 这条边终点也要加进来
            merge(e[j].u, e[j].v);
            if (find(s) == find(t)) {
                up_ans(e[j].w, e[i].w);
                break;
            }
        }
    }
    if (up % dw == 0)    print(up / dw);
    else printf("%lld/%lld\n", up / gcd(up, dw), dw / gcd(up, dw));
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}