codevs 1001 舒适的路线

目录

1. 输入描述 Input Description
2. 输出描述 Output Description
3. 样例输入 Sample Input
4. 样例输出 Sample Output
5. 数据范围及提示 Data Size & Hint

题解

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

题解

结构体数组存边。按照限速从大到小排序。

双重循环遍历 i：0 -> m，j：i + 1 -> m
循环内先在并查集上把第 i 条边的两个点连通，检查题目的源点和目标点是否联通，如果联通就已经找到了最优解，没有联通就依次联通 i + 1 一直到 m 的边，并不断检查是否满足条件。
边最大值就是第 i 条边的限速，最小值就是等到源点和目标点联通后的第一个边的限速。这里最大值不一定是最优的，最小是最优的。但是这并不影响结果，因为，下一次循环的时候 i 的值加一以后，最大值就会变化，整个循环中我们遍历了所有的可能的最大值。

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, fa[502], sz[502];
struct edge {
	int s, t, w;
} e[5003];

bool operator < (const edge &a, const edge &b) {
	return a.w > b.w;
}

void init() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i; sz[i] = 1;
	}
}

int getfa(int x) {
	if (fa[x] == x) return x;
	return fa[x] = getfa(fa[x]);
}

void merge(int x, int y) {
	int fx = getfa(x), fy = getfa(y);
	if (fx == fy) return;
	if (sz[fx] > sz[fy]) {
		fa[fy] = fx;
		sz[fx] += sz[fy];
	}
	else {
		fa[fx] = fy;
		sz[fy] += sz[fx];
	}
}

int gcd(int a, int b) {
    while (a > 0) {
    	int t = b % a;
    	b = a;
    	a = t;
    }
    return b;
}

int main() {
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
		cin >> e[i].s >>  e[i].t >>  e[i].w;
	int s, t;
	cin >> s >> t;
	sort(e, e+m);
	int maxw, minw, gmaxw, gminw;
	double cur_min = 1e10;
	bool flag = false;
	for (int i = 0; i < m; i ++) {
		init();
		maxw = e[i].w;
		merge(e[i].s, e[i].t);
		if (getfa(s) == getfa(t)) {
			gmaxw = e[i].w;
			gminw = e[i].w;
			flag = true;
			break;
		}
		int j = i + 1;
		while (j < m) {
			merge(e[j].s, e[j].t);
			if (getfa(s) == getfa(t)) {
				minw = e[j].w;
				flag = true;
				break;
			}
			j++;
		}
		if (j == m) break;
        double cur_v = maxw*1.0/minw;
        if (cur_v < cur_min) {
            gmaxw = maxw;
            gminw = minw;
            cur_min = cur_v;
		}
	}
	if (flag) {
		if (gmaxw % gminw == 0)
			cout << gmaxw / gminw << endl;
		else {
			int t = gcd(gmaxw, gminw);
			cout << gmaxw/t << '/' << gminw/t << endl;
		}
	}
	else 
		cout << "IMPOSSIBLE" << endl;
}

我参考了网上其他的代码，我比他多了一个优化，就是任意一次循环中无解马上退出。而且他的代码是有错误的，外层循环结束条件少了等号，所以下面的样例他的程序将得出错误答案，

2 1
1 2 1
1 2