题解 P2502 【[HAOI2006]旅行】

dailt · 2018-10-02 13:05:58 · 题解

这个题可以用最小生成树做

这个题是让我们找一条s,t的路径 ,使得这条路上的最大边和最小边的比值最小

那我们可以先固定一条最大边，然后不断向其中添加小边直到s，t联通

由于我们可以将小边从大到小枚举，每次判断s,t是否联通

那s,t一旦联通，此时的最大边和最小边就是一组可能的解啦

然后我们枚举所有最大边，将所有可行解找到，然后将他们比较一下就得出最优解啦

#include <iostream>
#include <cstdio>
#include <algorithm> 
#define re register     //放在循环前可以让你的循环更快一点 
using namespace std;
int n,m,fa[1010],s,t,rn,cnt,ansnum,vis[1010];
double ans=50000;
struct edge{int u,v,w;}e[10100];
struct anss{int maxx,minn;}aa[200000];
int gcd(int a,int b){       //最大公约数 约分用的~ 
    if(b==0)    return a;
    else return gcd(b,a%b); 
}
int getf(int a){    //找爹  顺便路径压缩一下 
    if(fa[a]==a)    return a;
    return fa[a]=getf(fa[a]);
} 
int cmp(edge a,edge b){return a.w<b.w;}
int main(){
    scanf("%d%d",&n,&m);
    for(re int i=1;i<=n;++i)    fa[i]=i,vis[i]=1;
    for(re int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[i].u=u,e[i].v=v,e[i].w=w;
        int fu=getf(u),fv=getf(v);//先把所有边连起来看看 s 和 t 是否联通 
        if(fu!=fv)  fa[fu]=fv;
    }
    scanf("%d%d",&s,&t);
    if(getf(s)!=getf(t)){           //判断是否联通 
        cout<<"IMPOSSIBLE";
        return 0;
    }
    int fs=getf(s);
    for(re int i=1;i<=n;++i)
        if(getf(i)!=fs) vis[i]=0;       //去掉没用的点（就是和s,t不连通的点 
    for(re int i=1;i<=n;++i)    fa[i]=i;    
    sort(e+1,e+m+1,cmp);
    for(re int i=1;i<=m;++i){           //固定最大边 
        if(!vis[e[i].u]||!vis[e[i].v])  continue;   //既然和s,t不连通那就不用这条边 
        for(re int j=1;j<=n;++j)    fa[j]=j; //记得初始化fa哦 
        for(re int j=i;j>=1;j--){       //寻找使s,t联通的最小边 
            int u=e[j].u,v=e[j].v;
            if(!vis[u]||!vis[v])    continue;
            int fu=getf(u),fv=getf(v);
            if(fu!=fv){
                fa[fu]=fv;
                int fs=getf(s),ft=getf(t);
                if(fs==ft){             //找到最小边 
                    aa[++cnt]=(anss){e[i].w,e[j].w};//添加到可行解中 
                    break;   
                } 
            }
        }
    }
    for(re int i=1;i<=cnt;++i){   //寻找并记录最优解 
        if(((double)aa[i].maxx/(double)aa[i].minn)<ans){
            ans=((double)aa[i].maxx/(double)aa[i].minn);
            ansnum=i;
        } 
    }
    if((aa[ansnum].maxx%aa[ansnum].minn)==0){//最优解是整数 
        cout<<aa[ansnum].maxx/aa[ansnum].minn;
    }
    else{//最优解不是整数 
        int a1=aa[ansnum].maxx/gcd(aa[ansnum].maxx,aa[ansnum].minn);
        int a2=aa[ansnum].minn/gcd(aa[ansnum].maxx,aa[ansnum].minn);
        cout<<a1<<"/"<<a2;
    }
    return 0;
}