rt, 点1 wa.

提交记录

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

const int MAXN = 500 + 7;
const int MAXM = 5e3 + 7;
int n, m, s, t, ans[200007][2], tot = 0;
int fa[MAXN];

int gcd(int x, int y)
{
	return y ? gcd(y, x % y) : x;
}

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

struct edge
{
	int u, v, w;
} e[MAXM];

bool cmp(edge a, edge b)
{
	return a.w > b.w;
}

void debug()
{
	cout << endl;
	for (int i = 1; i <= m; i ++)
		printf("%d %d %d %d\n", i, e[i].u, e[i].v, e[i].w);
	cout << endl;
}

int main()
{
	cin >> n >> m;
	
	for (int j = 1; j <= n; j ++) 
		fa[j] = j;
	
	for (int i = 1; i <= m; i ++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		fa[find(u)] = find(v);
		e[i].u = u, e[i].v = v, e[i].w = w;
	}
	
	cin >> s >> t;
	
	if (find(s) != find(t)) 
	{
		cout << "IMPOSSIBLE";
		return 0;
	}
	
	sort(e + 1, e + 1 + m, cmp);
	
//	debug();
	
	for (int i = 1; i < m; i ++)
	{
		int w1 = e[i].w, w2 = 0;
		
		for (int j = 1; j <= n; j ++) 
			fa[j] = j;
			
		fa[e[i].u] = e[i].v;
		
		for (int j = i + 1; j <= m; j ++)
		{
			int xx = find(e[j].u), yy = find(e[j].v);
			if (xx != yy) 
				fa[xx] = yy;
			if (find(s) == find(t))
			{
				w2 = e[j].w;
				break;
			}
		}
		
		ans[++ tot][0] = w1, ans[tot][1] = w2;
		int d = gcd(ans[tot][0], ans[tot][1]);
		ans[tot][0] /= d, ans[tot][1] /= d;
	}
	
	int realAns = 1;
	for (int i = 2; i <= tot; i ++) 
		if(ans[realAns][0] * ans[i][1] > ans[realAns][1] * ans[i][0])
			realAns = i;
	
	if (ans[realAns][1] == 1) cout << ans[realAns][0];
	else cout << ans[realAns][0] << '/' << ans[realAns][1];
	
	return 0;
}