算法：并查集
难度：NOIP
题解：
将所有边权从小到大排序，正序枚举最小边，在以第i条边为最短边的情况下，枚举j（权值比i大的边），用并查集维护全图的连通性，如果s，t已经连通，并且做到可以更新答案，那么就可以break了，因为继续枚举j是没有意义的，计算出的答案一定比现在的答案大（因为我们之前把边权从小到大排序了！）。这样我们通过枚举以i为最短边，维护s，t连通性，完美的求出了最优解！
时间复杂度：
代码如下：
居然因为gcd敲错了调了30min<"????">
#include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #define ll long long #define N 5005 using namespace std; struct node { int x,y,v; }edg[N]; int cmp(node x,node y) { return x.v<y.v; } int fa[N]; int findf(int x) { if(x==fa[x]) return x; return fa[x]=findf(fa[x]); } int gcd(int a,int b){return b?gcd(b,a%b):a;} int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 1;i <= m;i++) { scanf("%d%d%d",&edg[i].x,&edg[i].y,&edg[i].v); } sort(edg+1,edg+1+m,cmp); int s,t,minn=0,maxn=0; double ans=999999999.0000; scanf("%d%d",&s,&t); for(int i = 1;i <= m;i++) { for(int j = 1;j <= n;j++) { fa[j]=j; } for(int j = i;j <= m;j++) { int t1=findf(edg[j].x); int t2=findf(edg[j].y); if(t1!=t2) { fa[t1]=t2; } if(findf(s)==findf(t)) { if((double)edg[j].v/edg[i].v<ans) { ans=(double)edg[j].v/edg[i].v; minn=edg[i].v; maxn=edg[j].v; break; } } } } if(!maxn) puts("IMPOSSIBLE"); else { int gd=gcd(minn,maxn); if(minn/gd!=1) printf("%d/%d",maxn/gd,minn/gd); else printf("%d\n",maxn/gd); } return 0 ; }
