NO IMAGE

【題目】

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&Output

【樣例1】

輸入
4 2
1 2 1
3 4 2
1 4

輸出
IMPOSSIBLE 

【樣例2】

輸入
3 3
1 2 10
1 2 5
2 3 8
1 3

輸出
5/4

【樣例3】

輸入
3 2
1 2 2
2 3 4
1 3

輸出
2

 

【分析】

其實這道題我一開始無從下手,經dzy大佬講解以後,哇,茅塞頓開

主要是這道題裡面的 N,M 都是比較小的,那我們有一種偏暴力的演算法

對邊權從小到大排序,列舉最小邊,然後按順序把比它大的邊加進來,直到 s 能到達 t,這時最大邊就是最後加進來的邊

時間複雜度:O(m * m * α(n))

α(n)可以看成一個常數

 

【程式碼】

要注意的地方可以通過樣例分析出來

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 505
#define M 10005
using namespace std;
int n,m,s,t,num;
int rank[N],father[N];
struct node
{
int u,v,w;
}a[M];
bool comp(const node &p,const node &q)
{
return p.w<q.w;
}
int gcd(int a,int b)
{
int r=a%b;
while(r!=0)
{
a=b;
b=r;
r=a%b;
}
return b;
}
int find(int x)
{
if(father[x]==x)  return x;
return father[x]=find(father[x]);
}
void merge(int x,int y)
{
x=find(x);
y=find(y);
if(rank[x]<rank[y])
swap(x,y);
father[y]=x;
if(rank[x]==rank[y])
rank[x]  ;
}
int main()
{
int x,y,i,j,k,minn,maxn;
double now,ratio=1e 20;
scanf("%d%d",&n,&m);
for(i=1;i<=m;  i)
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
scanf("%d%d",&s,&t);
sort(a 1,a m 1,comp);
for(i=1;i<=m;  i)
{
for(j=1;j<=n;  j)
{
rank[j]=0;
father[j]=j;
}
for(j=i;j<=m;  j)
{
merge(a[j].u,a[j].v);
if(find(s)==find(t))
{
now=a[j].w*1.0/a[i].w*1.0;
if(ratio>now)
{
ratio=now;
minn=a[i].w;
maxn=a[j].w;
}
}
}
}
if(ratio==1e 20)
printf("IMPOSSIBLE");
else
{
k=gcd(minn,maxn);
maxn/=k;
minn/=k;
if(minn==1)  printf("%d",maxn);
else  printf("%d/%d",maxn,minn);
}
return 0;
}