[HAOI2006]旅行 暴力枚举+并查集维护联通

题解：
暴力枚举+并查集维护联通
由于本题点的范围不大，并且边的范围在5000以内。
这样的话我们可以采用复杂度的算法。
类似于贪心的方法，把边权从小到大排序。
因为这个题目只取决于最大最小值，两者比值越小越好。
我们把边权挨着枚举一遍即可。
从边权最小开始枚举，用并查集维护，每次加入一条边，并且检查s与t是否连接起来，如果连接起来，那么直接与当前最小比较一下然后break。
break后，再从次小边开始枚举......再从第三小......直到枚举完所有边即可。
所有的情况都枚举过，所以可以确保一定包含最接近题目要求的值

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int maxn=1e4+10;

struct edge{
    int x,y,w;
    bool operator < (const edge & a)const{
    return w<a.w;
    }
}a[maxn];


int f[maxn];

int ifind(int x){
    if(x==f[x]) return x;
    return f[x]=ifind(f[x]);
}



signed main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,v;
        cin>>x>>y>>v;
        a[i]={x,y,v};
    }
    sort(a,a+m);
    int s,t;
    cin>>s>>t;
    int imax=30000,imin=1;
    for(int i=0;i<m;i++){
        for(int i=0;i<=n;i++) f[i]=i;
        int tmin=a[i].w;
        for(int j=i;j<m;j++){
            int dx=ifind(a[j].x);
            int dy=ifind(a[j].y);
            if(dx!=dy) f[dx]=dy;
            if(ifind(s)==ifind(t)){
                int temp=imin*tmin;
                if(imax*temp/imin>a[j].w*temp/tmin){
                    int gcd=__gcd(tmin,a[j].w);
                    imax=a[j].w/gcd;
                    imin=tmin/gcd;
                }
                break;
            }
        }
    }
    if(imax==30000) cout<<"IMPOSSIBLE"<<endl;
    else{
        if(imin==1) cout<<imax<<endl;
        else cout<<imax<<"/"<<imin<<endl;
    }
}