前置知识

这道题的解法为：并查集 + 排序 + 二分

难度: 3 星

主要做法

首先考虑如何判断无解，很明显，无解的情况就是无论怎么样都不能从起点到终点，那么就是起点和终点在整个图中不连通，那么这种情况下输出"IMPOSSIBLE"，其余情况皆有解。

题目要求最大边与最小边的比值最小，所以我们不妨可以 枚举最小边 最大边，笔者选择的是枚举最小边。

因为此刻我们通过枚举已经确定的最小边，所以我们现在要最小化最大边。

在使用 的时候，加入的最后一条边就是整个生成树里面最大的一条边，在这道题里面最后加入的一条边的性质是什么呢？

不难想到加入的最后一条边一定是加入它之后使得终点和起点都联通了，这时候它就是最后一条边。

于是我们想到用同样的思路，先把边排序，然后从小到大枚举每一条边作为最小边的情况，然后不停的加边权大于等于它的边，倘若起点与终点已经联通，我们就停止加边，因为是 无向图，判断连通性用并查集即可。

然后用枚举到的最大边除以当前枚举到的最小边去更新答案，如果比答案更优，就记录下此时的最大边权和最小比权。

时间复杂度是：O( * 反阿克曼函数)。

如何比较两个分数的大小？

众所周知：假如 : 都大于

那么

所以得到:

是因为这里的边权较小，并不需要开，所以交叉相乘更方便。

对于此题的分析到此结束。

Code

#include <bits/stdc++.h>
using namespace std;

int n , m , cnt = 0,Ansa = 300001 ,Ansb = 1;//这个初值很讲究，不能爆int，也要恰好大于30000，于是就有了这个初值
int fa[505],s,t;

struct Edge {
    int from,to,w;
    bool operator < (const Edge& E) { return E.w > w;}
    void add(int u,int v, int W) { from = u , to = v , w = W; return ;}
} edge[10005];//双向边，记得开两倍空间

int find(int x) {
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];//路径压缩版的并查集
}

bool pd(int u,int v) {
    if(find(u) == find(v)) return 1;//判断u，v是否在同一个并查集中
    return 0;
}

void reset() {
    for(int i = 1 ; i <= n ; i ++) fa[i] = i;//重置并查集
    return ;
}

int main() {
    cin >> n >> m;
    reset();
    for(int i = 1 ; i <= m ; i ++) {
        int u , v , w;
        cin >> u >> v >> w;
        edge[++cnt].add(u,v,w);
        edge[++cnt].add(v,u,w);
        fa[find(u)] = find(v);//先合并，为了判断s，t的连通性
    }
    cin >> s >> t;
    if(!pd(s,t)) {
        cout << "IMPOSSIBLE";//如果在图中不连通，肯定无解
        return 0;
    }
    if(s == t){ cout << 0 ;return 0; }
    sort(edge + 1 , edge + 1 + cnt);//按照边权从小到大排序
    for(int i = 1 ; i < cnt ; i ++) { //枚举最小边
        int k,flag = 0;reset();
        for(int j = i ; j <= cnt ; j ++) {
            if(pd(s,t)) {flag = 1 ; break;}
            k = j;
            fa[find(edge[j].from)] = find(edge[j].to);
        }
        if(!flag) break;//假设已经不能用大于等于这个最小值的边权的边使得起点和终点联通，就没必要枚举了。
        int a = Ansa , b = Ansb , c = edge[k].w , d = edge[i].w;
        if(a * d - b * c > 0)//对应上面的柿子
        Ansa = edge[k].w , Ansb = edge[i].w;
    }
    if(Ansa % Ansb == 0) cout << Ansa / Ansb;//恰好能够整除按照题目要求是输出一个整数
    else cout << Ansa / __gcd(Ansa,Ansb) << "/" << Ansb / __gcd(Ansa,Ansb);//计算答案
    return 0;
}