先按边长排序，假设s与t连通，那么我们可以枚举s与t的路径中最短的一条边，通过类似与kruskal的方法找到s与t的路径在当前最小边权情况下尽量小的最大边权，用这个比值更新答案。
特别的，我们对于某一情况，如果循环完边之后s与t不连通可以跳出。在确定了最小边找完最大边的时候，不必要继续枚举最小边+1，可以从最大边开始向前加边，找到最大的边保证s，t连通，且最大边为刚才求得的，更新答案，从这个边继续枚举。这两个为优化。
反思：判断更新答案的时候手残打错，找了快一个小时才找到错。
/************************************************************** Problem: 1050 User: BLADEVIL Language: C++ Result: Accepted Time:772 ms Memory:868 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <algorithm> #define maxn 600 #define maxm 5010 using namespace std; int n,m,s,t; int father[maxn]; int ans1,ans2; struct rec { int a,b,len; } c[maxm]; bool cmp(rec a,rec b) {return (a.len<b.len);} int getfather(int x) { if (father[x]==x) return x; return father[x]=getfather(father[x]); } int gcd(int x,int y) { if (y>x) return gcd(y,x); if (!y) return x; return gcd(y,x%y); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].len); scanf("%d%d",&s,&t); sort(c+1,c+1+m,cmp); for (int i=1;i<=m;i++) { int j; for (j=1;j<=n;j++) father[j]=j; for (j=i;j<=m;j++) { int fa,fb; fa=getfather(c[j].a); fb=getfather(c[j].b); if (fa==fb) continue; father[fa]=fb; if (getfather(s)==getfather(t)) break; } if ((i==1)&&(getfather(s)!=getfather(t))) { printf("IMPOSSIBLE "); return 0; } if (getfather(s)!=getfather(t)) break; if (ans1*c[i].len>=ans2*c[j].len) ans1=c[j].len,ans2=c[i].len; } int x=gcd(ans1,ans2); if (x==ans2) printf("%d ",ans1/ans2); else printf("%d/%d ",ans1/x,ans2/x); return 0; }