BZOJ-1050: [HAOI2006]旅行comf

Description

给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<=30000)。给你两个顶点S和T，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。

m^2可过。枚举最小边，找最小的最大边使得s->t联通。计算答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t,fa[510],fz=30000,fm=1;
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
struct node
{
    int x,y,z;
}a[5100];
inline bool cmp(node x,node y){return x.z<y.z;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+m+1,cmp); scanf("%d%d",&s,&t); int x,y;
    for(int i=1;i<=m;++i)
    {
        int ans=0;
        for(int j=1;j<=n;++j) fa[j]=j;
        for(int j=i;j<=m;++j)
        {
            x=find(a[j].x); y=find(a[j].y);
            if(x!=y)
            {
                fa[x]=y;
                x=find(s); y=find(t);
                if(x==y){ans=j; break;}
            }
        }
        if(ans)
        {
            if(a[ans].z*fm<a[i].z*fz)
            {
                fz=a[ans].z;
                fm=a[i].z;
                int tmp=gcd(fz,fm);
                fz/=tmp; fm/=tmp;
            }
        }
    }
    if(fz==30000&&fm==1) puts("IMPOSSIBLE");
    else if(fm!=1) printf("%d/%d",fz,fm);
    else printf("%d",fz);
    return 0;
}