题解:
暴力枚举+并查集维护联通
由于本题点的范围不大,并且边的范围在5000以内。
这样的话我们可以采用复杂度的算法。
类似于贪心的方法,把边权从小到大排序。
因为这个题目只取决于最大最小值,两者比值越小越好。
我们把边权挨着枚举一遍即可。
从边权最小开始枚举,用并查集维护,每次加入一条边,并且检查s与t是否连接起来,如果连接起来,那么直接与当前最小比较一下然后break。
break后,再从次小边开始枚举......再从第三小......直到枚举完所有边即可。
所有的情况都枚举过,所以可以确保一定包含最接近题目要求的值
/*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define endl '\n' #define int long long using namespace std; const int maxn=1e4+10; struct edge{ int x,y,w; bool operator < (const edge & a)const{ return w<a.w; } }a[maxn]; int f[maxn]; int ifind(int x){ if(x==f[x]) return x; return f[x]=ifind(f[x]); } signed main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int x,y,v; cin>>x>>y>>v; a[i]={x,y,v}; } sort(a,a+m); int s,t; cin>>s>>t; int imax=30000,imin=1; for(int i=0;i<m;i++){ for(int i=0;i<=n;i++) f[i]=i; int tmin=a[i].w; for(int j=i;j<m;j++){ int dx=ifind(a[j].x); int dy=ifind(a[j].y); if(dx!=dy) f[dx]=dy; if(ifind(s)==ifind(t)){ int temp=imin*tmin; if(imax*temp/imin>a[j].w*temp/tmin){ int gcd=__gcd(tmin,a[j].w); imax=a[j].w/gcd; imin=tmin/gcd; } break; } } } if(imax==30000) cout<<"IMPOSSIBLE"<<endl; else{ if(imin==1) cout<<imax<<endl; else cout<<imax<<"/"<<imin<<endl; } }