首页 > 代码库 > BZOJ 1050 旅行comf(枚举最小边-并查集)

BZOJ 1050 旅行comf(枚举最小边-并查集)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1050

题意:给出一个带权图。求一条s到t的路径使得这条路径上最大最小边的比值最小?

思路:将边排序。枚举最小边,然后将边一个一个插到并查集里,s和t联通时计算更新答案。

 

struct node{    int u,v,w;    void get()    {        RD(u,v,w);    }};int cmp(node a,node b){    return a.w<b.w;}int n,m,s,t;node a[N*10];i64 Gcd(i64 x,i64 y){    return !y?x:Gcd(y,x%y);}int S[N];int get(int x){    if(S[x]!=x) S[x]=get(S[x]);    return S[x];}void Union(int x,int y){    x=get(x);    y=get(y);    if(x!=y) S[x]=y;}int main(){    RD(n,m);    int i,j;    FOR1(i,m) a[i].get();    sort(a+1,a+m+1,cmp);    RD(s,t);    i64 ansX=1,ansY=30000,temp;    int flag=0;    FOR1(i,m)    {        FOR1(j,n) S[j]=j;        FOR(j,i,m)        {            Union(a[j].u,a[j].v);            if(get(s)==get(t)) break;        }        if(j<=m)        {            flag=1;            if(ansY*a[i].w>ansX*a[j].w)            {                ansX=a[i].w;                ansY=a[j].w;            }        }    }    if(!flag) puts("IMPOSSIBLE");    else    {        temp=Gcd(ansX,ansY);        ansX/=temp;        ansY/=temp;        if(ansX==1) PR(ansY);        else printf("%lld/%lld\n",ansY,ansX);    }    return 0;}