Description

　　給你一個(gè)無向圖，N(N<=500)個(gè)頂點(diǎn), M(M<=5000)條邊，每條邊有一個(gè)權(quán)值Vi(Vi<30000)。給你兩個(gè)頂點(diǎn)S和T，求一條路徑，使得路徑上最大邊和最小邊的比值最小。如果S和T之間沒有路徑，輸出”IMPOSSIBLE”，否則輸出這個(gè)比值，如果需要，表示成一個(gè)既約分?jǐn)?shù)。 備注： 兩個(gè)頂點(diǎn)之間可能有多條路徑。

Input

　　第一行包含兩個(gè)正整數(shù)，N和M。下來的M行每行包含三個(gè)正整數(shù)：x，y和v。表示景點(diǎn)x到景點(diǎn)y之間有一條雙向公路，車輛必須以速度v在該公路上行駛。最后一行包含兩個(gè)正整數(shù)s，t，表示想知道從景點(diǎn)s到景點(diǎn)t最大最小速度比最小的路徑。s和t不可能相同。1<N<=500,1<=x,y<=N，0<v<30000，0<M<=5000

Output

　　如果景點(diǎn)s到景點(diǎn)t沒有路徑，輸出“IMPOSSIBLE”。否則輸出一個(gè)數(shù)，表示最小的速度比。如果需要，輸出一個(gè)既約分?jǐn)?shù)。

Sample Input

Sample Output

思路：

1、要一條從s到t的路徑，那么我們可以用生成樹來完成這個(gè)任務(wù)。

2、那么我們首先將邊按照從小到大排序。接下來枚舉最小權(quán)值邊，開始并查集處理并生成一顆使得從s到t連通的樹，那么最后一條入樹邊和第一條入樹邊就是這條路徑上的最小權(quán)值邊和最大權(quán)值邊。

過程維護(hù)最小比值，最終按照要求輸出即可。

Ac代碼：

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int f[505];struct node{    int x,y,w;}a[50005];int gcd(int x,int y){    if(y==0)return x;    else return gcd(y,x%y);}int find(int a){    int r=a;    while(f[r]!=r)    r=f[r];    int i=a;    int j;    while(i!=r)    {        j=f[i];        f[i]=r;        i=j;    }    return r;}int merge(int a,int b){    int A,B;    A=find(a);    B=find(b);    if(A!=B)    {        f[B]=A;    }}int cmp(node a,node b){    return a.w<b.w;}int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        double minn=1000000000000000000;        int flag=0;        int ans1,ans2;        for(int i=0;i<m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);        int s,e;        scanf("%d%d",&s,&e);        sort(a,a+m,cmp);        for(int l=0;l<m;l++)        {            int first=-1;            int final=0;            for(int i=1;i<=n;i++)f[i]=i;            for(int i=l;i<m;i++)            {                if(find(a[i].x)!=find(a[i].y))                {                    merge(a[i].x,a[i].y);                    if(first==-1)first=a[i].w;                    final=a[i].w;                }                if(find(s)==find(e))                {                    flag=1;                    int g=gcd(first,final);                    if(final*1.0/first*1.0<minn)                    {                        minn=final*1.0/first*1.0;                        ans1=first/g;                        ans2=final/g;                    }                }            }        }        if(flag==0)PRintf("IMPOSSIBLE/n");        else if(ans1==1)printf("%d/n",ans2);        else printf("%d/%d/n",ans2,ans1);    }}