题解:
暴力枚举+并查集维护联通
由于本题点的范围不大,并且边的范围在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;
}
}

京公网安备 11010502036488号