bzoj 1050 并查集

　　先按边长排序，假设s与t连通，那么我们可以枚举s与t的路径中最短的一条边，通过类似与kruskal的方法找到s与t的路径在当前最小边权情况下尽量小的最大边权，用这个比值更新答案。

　　特别的，我们对于某一情况，如果循环完边之后s与t不连通可以跳出。在确定了最小边找完最大边的时候，不必要继续枚举最小边+1，可以从最大边开始向前加边，找到最大的边保证s，t连通，且最大边为刚才求得的，更新答案，从这个边继续枚举。这两个为优化。

　　反思：判断更新答案的时候手残打错，找了快一个小时才找到错。

/**************************************************************

    Problem: 1050

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:772 ms

    Memory:868 kb

****************************************************************/

//By BLADEVIL

#include <cstdio>

#include <algorithm>

#define maxn 600

#define maxm 5010

using namespace std;

int n,m,s,t;

int father[maxn];

int ans1,ans2;

struct rec

{

    int a,b,len;

} c[maxm];

bool cmp(rec a,rec b)

{return (a.len<b.len);}

int getfather(int x)

{

    if (father[x]==x) return x;

    return father[x]=getfather(father[x]);

}

int gcd(int x,int y)

{

    if (y>x) return gcd(y,x);

    if (!y) return x;

    return gcd(y,x%y);

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=m;i++) scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].len);

    scanf("%d%d",&s,&t);

    sort(c+,c++m,cmp);

    for (int i=;i<=m;i++)

    {

        int j;

        for (j=;j<=n;j++) father[j]=j;

        for (j=i;j<=m;j++)

        {

            int fa,fb;

            fa=getfather(c[j].a); fb=getfather(c[j].b);

            if (fa==fb) continue;

            father[fa]=fb;

            if (getfather(s)==getfather(t)) break;

        }

        if ((i==)&&(getfather(s)!=getfather(t)))

        {

            printf("IMPOSSIBLE\n");

            return ;

        }

        if (getfather(s)!=getfather(t)) break;

        if (ans1*c[i].len>=ans2*c[j].len) ans1=c[j].len,ans2=c[i].len;

    }

    int x=gcd(ans1,ans2);

    if (x==ans2) printf("%d\n",ans1/ans2); else printf("%d/%d\n",ans1/x,ans2/x);

    return ;

}

巴特西

bzoj 1050 并查集

最新文章

热门文章