求助,此代碼爲何只有90分(或幫忙hack
查看原帖
求助,此代碼爲何只有90分(或幫忙hack
86973
花园Serena楼主2020/8/11 17:35
#include <bits/stdc++.h>
using namespace std;
struct node {
	int l, r, w;
}a[5000 + 10];
double Min = 0x7fffffff;
int minl, minr, f[500 + 10];
bool cmp (node x, node y) {
	return x.w < y.w;
}
int found (int x) {
	while (x != f[x])
		x = f[x] = f[f[x]];
	return x;
}
void mix (int x, int y) {
	f[found(x)] = found(y);
}
int gcd(int x, int y) {
	if (x > y) swap(x, y);
	if (y % x == 0) return x;
	return gcd (y % x, x); 
}
int main ()  {
	int n, m; scanf("%d%d", &n, &m);
	for(register int i = 1; i <= m; i ++)
		scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
	sort (a + 1, a + m + 1, cmp);
	int s, t; scanf("%d%d", &s, &t);
	for (register int i = m; i >= 1; i --) {
		for(register int j = 1; j <= n; j ++) f[j] = j;
		int x; for(x = i; x >= 1; x --) {
			if(found(a[x].l) != found(a[x].r))
				mix (a[x].l, a[x].r);
			if(found(s) == found(t)) break;
		}
		if(Min > (double) a[i].w / a[x].w && x >= 1) {
			Min = (double) a[i].w / a[x].w;
			minl = a[x].w; minr = a[i].w;
		}
	}
	if(Min == 0x7fffffff) {cout<<"IMPOSSBLE\n"; return 0;}
	int ans = gcd(minl, minr);
	minl /= ans; minr /= ans;
	if(minl == 1) printf("%d\n", minr);
	else {printf("%d/%d\n", minr, minl);}
	return 0;
}

RT 此上爲本題代碼,求解施爲何WA了第三個點,或者幫忙給個數據hack

2020/8/11 17:35
加载中...