题目
枚举最小边，在用kruskal方法来让S与T，联通，这样比值就最优了。。
#include<bits/stdc++.h> using namespace std; int f[501]; int n,m,s,t; int A1,A2; double Ans; bool have_Ans; struct edge{ int x; int y; int value; void read() { scanf("%d%d%d",&x,&y,&value); } };edge E[5001]; bool cmp(edge A,edge B) { return A.value<B.value; } int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } int GCD(int x,int y) { return y==0?x:GCD(y,x%y); } int main() { //freopen("in","r",stdin); scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) E[i].read(); sort(E+1,E+m+1,cmp); scanf("%d%d",&s,&t); have_Ans=false; Ans=100000000.0; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) f[j]=j; for(int j=i;j<=m;j++) { int fx=find(E[j].x),fy=find(E[j].y); if(fx!=fy)f[fy]=fx; if(find(s)==find(t)) { have_Ans=true; if(Ans>(double)E[j].value/E[i].value) { Ans=(double)E[j].value/E[i].value; A1=E[j].value; A2=E[i].value; } } } } if(!have_Ans)cout<<"IMPOSSIBLE"; else { int gcd=GCD(A1,A2); A1/=gcd,A2/=gcd; if(A2==1)cout<<A1; else cout<<A1<<"/"<<A2; } return 0; }