【BZOJ1050】[HAOI2006]旅行

题面

bzoj

洛谷

题解

先将所有边从小往大排序

枚举钦定一条最小边

再枚举依次枚举最大边，如果两个点联通了就(break)统计答案即可

代码

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm>
#include <vector> 
using namespace std;

const int MAX_N = 505; 
const int MAX_M = 5005;
int N, M, S, T, fa[MAX_N]; 
int getf(int x) { return (fa[x] == x) ? x : (fa[x] = getf(fa[x])); }
bool same(int x, int y) { return getf(x) == getf(y); }
void unite(int x, int y) { fa[getf(x)] = getf(y); } 
void clear() { for (int i = 1; i <= N; i++) fa[i] = i; } 
struct Edge { int u, v, w; } e[MAX_M];
bool operator < (const Edge &a, const Edge &b) { return a.w < b.w; } 
double ans = 1e9; 
int ansl, ansr; 
int main () { 
    scanf("%d%d", &N, &M); 
	for (int i = 1; i <= M; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	scanf("%d%d", &S, &T);
	sort(&e[1], &e[M + 1]); 
	for (int i = 1; i <= M; i++) {
		clear(); int j; 
		for (j = i; j <= M; j++) {
			int u = e[j].u, v = e[j].v; 
			if (!same(u, v)) unite(u, v); 
			if (same(S, T)) break; 
		}
		if ((ans > 1.0 * e[j].w / e[i].w) && same(S, T))
			ans = 1.0 * e[j].w / e[i].w, ansl = e[i].w, ansr = e[j].w; 
	} 
	if (ans == 1e9) puts("IMPOSSIBLE");
	else {
		int d = __gcd(ansl, ansr); 
		ansl /= d, ansr /= d; 
		if (ansl == 1) printf("%d
", ansr);
		else printf("%d/%d
", ansr, ansl); 
	} 
	return 0; 
}