给定一个无向图，求s到t间的一条路径，使得该路径上最大边和最小边的比值最小

将边按边权大小排序后，直接枚举枚举一个区间[ i , j ] (1 <= i <= j <= m )，用并查集判断s是否可以通过这个区间内的路径达到t。

#include
  
   
#include
   
     #include
    
      #include
     
       #define N 100000 #define INF 50000 using namespace std; int f[N], n, m, i, j, k, s, t, ans1, ans2, ljz; struct edge{ int u,v,c; }e[N]; int find(int x) { if (f[x] != x) f[x]=find(f[x]); return f[x]; } int gcd(int a,int b) { return (b > 0) ? gcd(b, a % b) : a; } bool cmp(edge a, edge b) { return a.c < b.c; } int main() { scanf("%d%d",&n,&m); for (i=1; i<=m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c); scanf("%d%d", &s, &t); ans1=INF; ans2=1; sort(e + 1, e + m + 1, cmp); for (i=1; i<=m; i++) { for (j=1; j<=n; j++) f[j]=j; for (j=i; j<=m; j++) { int fa=find(e[j].u), fb=find(e[j].v); f[fa]=fb; if (find(s) == find(t)) { if ((e[j].c * ans2) < (e[i].c * ans1)) ans1=e[j].c, ans2=e[i].c; break; } if (e[j].c * ans2 >= e[i].c * ans1) break; } } ljz=gcd(ans1, ans2); if (ans1 == INF) printf("IMPOSSIBLE"); else if (ans2 != ljz) printf("%d/%d",ans1 / ljz, ans2 / ljz); else printf("%d",ans1 / ans2); return 0; }