求最大边/最小边的比值最小的路径 codevs 1001 舒适的路线

时间:2022-05-12 20:52:58

codevs 1001 舒适的路线

2006年

 时间限制: 2 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
 
题目描述 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范围内

最最基本的思想:枚举最小边,把和它组合最好的最大边找出来,这样找到所有的最小最大值组合,从其中找到比例最小的。

网上的题解+注释:

 /*
其实这个题目看似是类似于最短路的问题,但实际上与最短路无关。
因为路是双向的,所以我们为了最优的比例,当然可以去走一条无关的路。
可以设计m^2的算法:
先将边按长度排序,然后每次枚举最小边的长度w[i]作限定,依次加入更大的边,
当加到某条边w[j]后,s与t连通(并查集判断),就用w[j]/w[i](double类型)更新答案
若没有w[i]能使s与t连通,则无解 注意:路径中分出的"杈"不用管,因为即使无关,我们也可以走(仅仅是为了那个比例),去掉后s,t仍连通,不会影响答案
*/
#include<stdio.h>
#include<stdlib.h>
int fa[]={},u[]={},v[]={},w[]={};
int father(int x)
{
if(fa[x]!=x) fa[x]=father(fa[x]);
return fa[x];
}
void jh(int* a,int* b)
{
int t=*a;
*a=*b;
*b=t;
}
void kp(int low,int high)
{
int i=low,j=high,mid=w[(i+j)/];
while(i<j)
{
while(w[i]<mid) i++;
while(w[j]>mid) j--;
if(i<=j)
{
jh(&u[i],&u[j]);
jh(&v[i],&v[j]);
jh(&w[i],&w[j]);
i++;
j--;
}
}
if(j>low) kp(low,j);
if(i<high) kp(i,high);
}
int gcd(int a,int b)
{
if(b==) return a;
return gcd(b,a%b);
}
int main()
{
int n,m,i,j,s,t,min=-,max=-;
scanf("%d%d",&n,&m);
for(i=;i<=m;i++)
scanf("%d%d%d",&u[i],&v[i],&w[i]);
scanf("%d%d",&s,&t);
kp(,m);
for(i=;i<=m;i++)//枚举最小边权:w[i]
{
if(w[i]==w[i-]) continue;/*快得不止一点点,这个剪枝,之所以正确,就是因为可以走无关的路,所以最小边的大小不变的话,再建一棵树,结果还是相同的。*/
for(j=;j<=n;j++)
fa[j]=j; /*每次都要建树,所以每次都把并查集初始化*/
for(j=i;j<=m;j++)
{
if(father(u[j])!=father(v[j])) fa[father(u[j])]=father(v[j]);
if(father(s)==father(t)) break; /*用并查集检验s-t是否联通来找的最长边,然后最短边是枚举的,那么就可以很轻易地求出比值了*/
}
if(j<=m&&(min==-||(double)max/(double)min>(double)w[j]/(double)w[i])) /*比值用double,更准*/
{
min=w[i];
max=w[j];
}
}
if(min==-) printf("IMPOSSIBLE");
else
{
if(max%min==) printf("%d",max/min);
else printf("%d/%d",max/gcd(max,min),min/gcd(max,min));
}
return ;
}

my代码:

 #include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>
#define N 505
#define M 5005
struct Edge{
int u,v,w;
bool operator<(Edge P)
const{return w<P.w;}
}edge[M];
int n,m,s,t,maxx=-,minn=-,father[N];
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
void input()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
scanf("%d%d",&s,&t);
}
int find(int x)
{
if(father[x]==x) return x;
return father[x]=find(father[x]);
}
bool kruskal()
{
sort(edge+,edge+m+);
for(int i=;i<=m;++i)
{
if(edge[i].w==edge[i-].w) continue;
int j;
for(j=;j<=n;++j)
father[j]=j;
for(j=i;j<=m;++j)/*j循环要从i开始,因为此时i这条边还没有加入到生成树中*/
{
int x1=find(edge[j].u),x2=find(edge[j].v);
if(x1!=x2)
{
father[x2]=x1;
}
if(find(s)==find(t)) break;
}
if(j<=m&&(minn==-||((double)maxx/(double)minn>(double)edge[j].w/(double)edge[i].w)))
{
minn=edge[i].w;
maxx=edge[j].w;
}
}
if(minn==-) return false;
return true;
}
int main()
{
input();
if(!kruskal())
printf("IMPOSSIBLE\n");
else {
if(maxx%minn==) printf("%d",maxx/minn);
else printf("%d/%d",maxx/gcd(maxx,minn),minn/gcd(maxx,minn));
}
return ;
}