CODEVS 1001 舒适的路线

题目描述 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范围内

并查集,每次枚举速度最大的边,然后逐个加入更小的边,直到联通,更新答案,然后删去当前最大的边,继续更新

#include <iostream>
#include <algorithm>
#include <cstdio>
long long	n, m, bcj[510], s, t, maxs, mins;
double		shang;
using namespace std;
struct edge {
	int x, y, v;
} edges[5010];
bool cmp( const edge &a, const edge &b )
{
	return(a.v > b.v);
}


int getfa( int n )
{
	if ( bcj[n] == n )
		return(n);
	return(bcj[n] = getfa( bcj[n] ) );
}


long long gcd( int a, int b )
{
	return(b ? gcd( b, a % b ) : a);
}


int main()
{
	shang = 1e9;
	scanf( "%d%d", &n, &m );
	for ( int i = 0; i < m; i++ )
		scanf( "%d%d%d", &edges[i].x, &edges[i].y, &edges[i].v );
	scanf( "%d%d", &s, &t );
	sort( edges, edges + n, cmp );
	for ( int i = 0; i < m; i++ )
	{
		for ( int j = 1; j <= n; j++ )
			bcj[j] = j;
		for ( int j = i; j < m; j++ )
		{
			bcj[edges[j].x] = getfa( edges[j].y );
			if ( getfa( s ) == getfa( t ) )
			{
				if ( shang > ( (edges[i].v * 1.0) / edges[j].v) )
				{
					shang	= (edges[i].v * 1.0) / edges[j].v;
					maxs	= edges[i].v;
					mins	= edges[j].v;
				}
				break;
			}
		}
		if ( getfa( s ) == getfa( t ) )
		{
			continue;
		}
		 
		break;
	}
	if ( maxs == 0 )
	{
		printf( "IMPOSSIBLE" );
		return(0);
	}
	long long gcdd = gcd( maxs, mins );
	maxs	/= gcdd;
	mins	/= gcdd;
	if ( mins == 1 )
	{
		printf( "%d", maxs );
		return(0);
	}
	printf( "%d/%d", maxs, mins );
}

 

此条目发表在CODEVS, 并查集分类目录。将固定链接加入收藏夹。