[bzoj1050][HAOI2006]旅行comf【MST】

【题目链接】
　　http://www.lydsy.com/JudgeOnline/problem.php?id=1050
【题解】
　　枚举最小值，把比它小的边都删去做一遍MST求出最大值，注意MST只要做到T连通。

/* --------------
    user Vanisher
    problem bzoj-1050
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    M       10010
# define    N       510
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
struct node{
    int u,v,w;
}e[M];
int f[N],n,m,s,t;
bool cmp(node x, node y){
    return x.w<y.w;
}
int dad(int x){
    if (f[x]==x) return x;
        return f[x]=dad(f[x]);
}
int gcd(int x, int y){
    if (x%y==0) return y;
        else return gcd(y,x%y);
}
int doit(int i){
    for (int i=1; i<=n; i++) f[i]=i;    
    int cnt=n;
    while (dad(s)!=dad(t)&&i<=m){
        int u=dad(e[i].u), v=dad(e[i].v);
        if (u!=v){
            cnt--;
            f[u]=v;
        }
        i++;
    }
    if (dad(s)==dad(t))
        return e[i-1].w;
        else return -1;
}
int main(){
    n=read(), m=read();
    for (int i=1; i<=m; i++)
        e[i].u=read(), e[i].v=read(), e[i].w=read();
    s=read(), t=read();
    sort(e+1,e+m+1,cmp);
    double ans=inf; int up, down;
    for (int i=1; i<=m; i++){
        int mx=doit(i);
        if (mx==-1) break;
        if (mx*1.0/e[i].w<ans){
            up=mx, down=e[i].w;
            ans=mx*1.0/e[i].w;
        }
    }
    if (ans==inf){
        printf("IMPOSSIBLE
");
        return 0;
    }
    int k=gcd(up,down);
    up/=k; down/=k;
    if (down==1)
        printf("%d
",up);
        else printf("%d/%d",up,down);
    return 0;
}