做法:类最小生成树
思路:
- 1.先将边从大到小排
- 2.枚举最大边,然后进行连边
- 3.每次连边,如果连玩次边后发现s和t联通,那么最小边就是该边,并退出Kruskal
- 4.依次比较ans与最大边与最小边的比值
- 5.如果最大边枚举到不存在最小边s和t联通,那么退出枚举最小边
代码
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout<<#a<<":"<<a<<"\n"
const int N=2e5+10,INF=0x3f3f3f3f;
int n,m,s,t,fa[N],depth[N];
int maxx,minn,fz=-1,fm=-1;
double ans=INF;
struct edge{
int u,v,w;
}e[N];
bool cmp(edge x,edge y){
return x.w>y.w;
}
void init(int n){
for(int i=1;i<=n;i++)
fa[i]=i,depth[i]=1;
}
//查询树的根
int find(int x){
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
//合并a和b所属的集合
void unite(int a,int b){
a=find(a),b=find(b);
if(depth[a]==depth[b]){
depth[a]=depth[a]+1;
fa[b]=a;
}
else{
if(depth[a]<depth[b]) fa[a]=b;
else fa[b]=a;
}
}
//判断a和b是否属于同一个集合
bool same(int a,int b){
return find(a)==find(b);
}
int Kruskal(int x){
for(int i=x;i<m;i++){
unite(e[i].u,e[i].v);
if(same(s,t)) return e[i].w;
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
cin>>s>>t;
sort(e,e+m,cmp);
for(int i=0;i<m;i++){
init(n);
maxx=e[i].w;
minn=Kruskal(i);
if(minn==-1) break;
if(1.0*maxx/minn<ans) fz=maxx,fm=minn,ans=1.0*maxx/minn;
}
if(fz==-1&&fm==-1) puts("IMPOSSIBLE");
else{
int gcd=__gcd(fz,fm);
if(fm/gcd==1) cout<<fz/gcd<<"\n";
else cout<<fz/gcd<<"/"<<fm/gcd<<"\n";
}
return 0;
}