这道题的意思是给定一张图，求所有从s到t的路径中最大边与最小边的比值的最小值。首先对于确定的一个最小边，我们想让比值最小，就需要让最大边最小，容易想到求最小生成树，先将边按边权从小到大排序，然后枚举最小边，再用并查集维护，当s与t在同一个连通块里时，记录当前最大边，更新答案。还有一个问题是枚举的最小边不一定在s到t的路径中，不过这是没有问题的，假设i是s到t路径中的最小值，j在i前面，j是我们当前枚举的最小值，可以知道从i和j枚举最终最大边都会是k，而v[i]>v[j]，因此i的答案会更新掉j的答案，这样就保证了答案的正确性
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 50000 struct edge { int fr,to,v; }e[maxn]; int n,m,s,t,ans1,ans2,temp1,temp2,father[maxn]; double ans=1e9; int gcd(int x,int y) { if (y==0) return x; return gcd(y,x%y); } int getfather(int x) { if (x!=father[x]) father[x]=getfather(father[x]); return father[x]; } bool cmp(edge a,edge b) { return a.v<b.v; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&e[i].fr,&e[i].to,&e[i].v); sort(e+1,e+m+1,cmp); scanf("%d%d",&s,&t); for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) father[j]=j; temp1=e[i].v; for (int j=i;j<=m;j++) { int x=e[j].fr; int y=e[j].to; x=getfather(x); y=getfather(y); if (x==y) continue; father[x]=y; if (getfather(s)==getfather(t)) { temp2=e[j].v; double p=(double)temp2/temp1; if (p<ans) { ans=p; ans1=temp1; ans2=temp2; } break; } } } if (ans2==0) { printf("IMPOSSIBLE\n"); return 0; } int k=gcd(ans1,ans2); if (k==ans1) printf("%d\n",ans2/ans1); else { ans1/=k;ans2/=k; printf("%d/%d\n",ans2,ans1); } return 0; }