最舒适的路线

题目描述

异形卵潜伏在某区域的一个神经网络中。其网络共有N个神经元（编号为1,2,3,…,N），这些神经元由M条通道连接着。两个神经元之间可能有多条通道。异形卵可以在这些通道上来回游动，但在神经网络中任一条通道的游动速度必须是一定的。当然异形卵不希望从一条通道游动到另一条通道速度变化太大，否则它会很不舒服。

现在异形卵聚居在神经元S点，想游动到神经元T点。它希望选择一条游动过程中通道最大速度与最小速度比尽可能小的路线，也就是所谓最舒适的路线。

输入

第一行： K     表示有多少组测试数据。 

接下来对每组测试数据：

第1行:       N  M

第2~M+1行： Xi  Yi  Vi   (i=1,…..,M)

表示神经元Xi 到神经元Yi之间通道的速度必须是Vi

最后一行：     S  T    

  2≤K≤5   1<N≤500   0<M≤5000   1≤ Xi, Yi , S , T ≤N   0< Vi <30000，

  Vi是整数。数据之间有一个空格。

输出

对于每组测试数据，输出一行：如果神经元S到神经元T没有路线，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

样例输入

2
3 2
1 2 2
2 3 4
1 3
3 3
1 2 10
1 2 5
2 3 8
1 3

样例输出

2
5/4

题意描述：

已知n个点和m条边，点a到点b的速度为v，问能否从s点到达t点，且使得行走过程中道路的最大速度/最小速度最小。

解题思路：

并查集判断能否从s点到达t点，枚举判断最大值与最小值的比值。

具体思路：先将m条边按速度降序排列，从第一条边开始枚举，当能从s找到t时，比较此路径其中的最大速度与最小速度的比值，一直枚举比较，最后查找到最后结果。

程序代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
# define inf 99999999
using namespace std;
int f[550];
struct A
{
	int a;
	int b;
	int v;
}q[5050];
int cmp(A a,A b)
{
	return a.v>b.v;
}
int get_f(int i)
{
	if(f[i]==i)
		return i;
	else
	{
		f[i]=get_f(f[i]);
		return f[i];
	}
}
void merge(int u,int v)
{
	int t1,t2;
	t1=get_f(u);
	t2=get_f(v);
	if(t1!=t2)
		f[t2]=t1;
}
int gcd(int x,int y)
{
	if(x%y)
		return gcd(y,x%y);
	return y;
}
int main()
{
	int n,m,i,j,u,max,min,k,s,t;
	double ans;
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++)
			scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].v);
		scanf("%d%d",&s,&t);
		sort(q+1,q+m+1,cmp);
		ans=inf*1.0;
		for(i=1;i<=m;i++)
		{
			for(u=1;u<=n;u++)
				f[u]=u;
			for(j=i;j<=m;j++)
			{
				merge(q[j].a,q[j].b);
				if(get_f(s)==get_f(t))
					break;
			}
			if(j==m+1)
				break;
			if(q[i].v*1.0/q[j].v<ans)
			{
				max=q[i].v;
				min=q[j].v;
				ans=q[i].v*1.0/q[j].v;
			}
		}
		if(ans==inf*1.0)
			printf("IMPOSSIBLE\n");
		else
		{
			if(max%min)
			{
				u=gcd(max,min);
				printf("%d/%d\n",max/u,min/u);
			}
			else
				printf("%d\n",max/min);
		}
	}
}