Description

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

Input

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

Output

　　如果景點s到景點t沒有路徑，輸出“IMPOSSIBLE”。否則輸出一個數，表示最小的速度比。如果需要，輸出一個既約分數。

Sample Input

Sample Output

思路：

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

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

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

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);    }}