Little Busters! — 并查集

题目链接：http://acm.buaa.edu.cn/problem/418/

 

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn = 550;
const int maxe = 5050;
const int INF = 0x3f3f3f3f;int pa[maxn];
int find(int x)
{return x == pa[x] ? x : pa[x] = find(pa[x]);
}
struct Edge
{int u,v,w;bool operator < (const Edge& rhs) const{return w > rhs.w;}
} e[maxe];int s,t;
int n,m;
int Max,Min;void solve()
{for(int i=1; i<=m; i++){for(int j=1; j<=n; j++) pa[j] = j;int j;for(j=i; j<=m; j++){int ufa = find(e[j].u);int vfa = find(e[j].v);if(ufa != vfa){pa[vfa] = ufa;}if(find(s) == find(t)) break;}if(j > m) return;if(Max*e[j].w > Min*e[i].w){Max = e[i].w;Min = e[j].w;}}
}int main()
{//freopen("/home/raidy/桌面/shaynelq/beihang8_contest/input.txt","r",stdin);int T;cin>>T;while(T --){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);}sort(e+1,e+m+1);scanf("%d %d",&s,&t);Max = 30000,Min = 0;solve();if(Max == 30000 && Min == 0){printf("R U Kiddin'?\n");continue;}int g = __gcd(Max,Min);Max /= g;Min /= g;if(Min == 1) printf("%d\n",Max);else         printf("%d/%d\n",Max,Min);}
}