[HAOI2006]旅行COMF

做法：类最小生成树

思路：

• 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;
}