[codevs1001]舒适的路线

试题描述

Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

输入

第一行包含两个正整数，N和M。
接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

输出

如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

输入示例

输出示例

数据规模及约定

N(1<N≤500)

M（0<M≤5000）

Vi在int范围内

题解

把 m 条边按照 V 值从小到大排序，然后 O(n²) 扫一遍用并查集维护一下 s, t 间的连通性。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 510

#define maxm 5010

#define LL long long

int n, m, s, t;

struct Edge {

	int u, v, d;

	Edge() {}

	Edge(int _1, int _2, int _3): u(_1), v(_2), d(_3) {}

	bool operator < (const Edge& t) const { return d < t.d; }

} es[maxm];

LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }

struct Fra {

	LL a, b;

	Fra() {}

	Fra(LL _, LL __): a(_), b(__) {}

	void maintain() {

		if(a < 0) return ;

		LL d = gcd(a, b);

		a /= d; b /= d;

		return ;

	}

	bool operator < (const Fra& t) const { return a * t.b < b * t.a; }

} ;

int fa[maxn];

int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }

int main() {

	n = read(); m = read();

	for(int i = 1; i <= m; i++) {

		int a = read(), b = read(), c = read();

		es[i] = Edge(a, b, c);

	}

	s = read(); t = read();

	Fra ans(-1, -1);

	sort(es + 1, es + m + 1);

	for(int i = 1; i <= m; i++) {

		for(int j = 1; j <= n; j++) fa[j] = j;

		for(int j = i; j <= m; j++) {

			Edge& e = es[j];

			int u = findset(e.u), v = findset(e.v);

			if(u != v) fa[v] = u;

			if(findset(s) == findset(t)) {

				if(ans.a < 0) ans = Fra(e.d, es[i].d);

				ans = min(ans, Fra(e.d, es[i].d));

				break;

			}

		}

	}

	if(ans.a < 0) return puts("IMPOSSIBLE"), 0;

	ans.maintain();

	if(ans.b != 1) printf("%lld/%lld\n", ans.a, ans.b);

	else printf("%lld\n", ans.a);

	return 0;

}

秒客网

[codevs1001]舒适的路线

相关文章