CODEVS 1001 舒适的路线

题目描述 Description

 

Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z小镇附近共有N(1<N≤500)个

景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个

景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给

定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大

家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，

也就是所谓最舒适的路线。

 

输入描述 Input Description

 

第一行包含两个正整数，N和M。
接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示

想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

输出描述 Output Description

如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

 

样例输入 Sample Input

样例1
4 2
1 2 1
3 4 2
1 4

样例2
3 3
1 2 10
1 2 5
2 3 8
1 3

样例3
3 2
1 2 2
2 3 4
1 3

样例输出 Sample Output

样例1
IMPOSSIBLE

样例2
5/4

样例3
2

数据范围及提示 Data Size & Hint

N(1<N≤500)

M（0<M≤5000）

Vi在int范围内

题目大意：求连接s-t的一条路径的最大边长/最小边长最小

题解：枚举+并查集

最大最小值是不适合01分数规划的

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 520
using namespace std;

int n,m,s,t,fz,fm;

double ans=10000000.;

int fa[N];

struct E{
    int x,y,z;
}e[N*10];

bool cmp(E a,E b){
    return a.z<b.z;
}

int f(int x){
    return fa[x]==x?x:fa[x]=f(fa[x]);
}

void clear_(){
    for(int i=1;i<=n;i++)fa[i]=i;
}

int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

int main(){
    scanf("%d%d",&n,&m);clear_();
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
        int x=f(e[i].x),y=f(e[i].y);
        fa[x]=y;
    }
    scanf("%d%d",&s,&t);
    if(f(s)!=f(t)){
        printf("IMPOSSIBLE
");
        return 0;
    }
    sort(e+1,e+m+1,cmp);clear_();
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j++){
            fa[f(e[j].x)]=f(e[j].y);
            if(f(s)==f(t)){
                double zz;zz=e[j].z*1./e[i].z;
                if(zz<ans){
                    ans=zz;fz=e[j].z;fm=e[i].z;
                }
                break;
            }
        }clear_();
    }
    int gg=gcd(fz,fm);fz=fz/gg;fm=fm/gg;
    if(fm==1)printf("%d
",fz);
    else printf("%d/%d",fz,fm);
    return 0;
}