LightOJ 1029 【最小生成树】

思路：

利用克鲁斯卡尔算法，最小生成树把边从小到大排序，然后Union；

最大生成树就是把边从大到小排序，然后Union；

#include<bits/stdc++.h>

using namespace std;

typedef __int64 LL;

const int N=15000;

struct asd{

    int u,v;

    int w;

};

asd q[N];

int pre[N],n,num;

bool cmp(asd x,asd y)

{

    return x.w<y.w;

}

void init()

{

    for(int i=0;i<=n;i++)

        pre[i]=i;

}

int Find(int x)

{

    int r=x;

    while(pre[r]!=r)

        r=pre[r];

    int i=x,j;

    while(pre[i]!=r)

    {

        j=pre[i];

        pre[i]=j;

        i=j;

    }

    return r;

}

int max_tree()

{

    int ans=0;

    init();

    for(int i=num-1;i>=0;i--)

    {

        int aa=Find(q[i].u);

        int bb=Find(q[i].v);

        if(aa!=bb)

        {

            pre[aa]=bb;

            ans+=q[i].w;

        }

    }

    return ans;

}

int min_tree()

{

    int ans=0;

    init();

    for(int i=0;i<num;i++)

    {

        int aa=Find(q[i].u);

        int bb=Find(q[i].v);

        if(aa!=bb)

        {

            pre[aa]=bb;

            ans+=q[i].w;

        }

    }

    return ans;

}

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        num=0;

        int a,b,c;

        while(scanf("%d%d%d",&a,&b,&c))

        {

            if(!a&&!b&&!c) break;

            q[num].u=a;

            q[num].v=b;

            q[num].w=c;

            num++;

        }

        sort(q,q+num,cmp);

        int q,p;

        q=max_tree()+min_tree();

        if(q%2)

            printf("Case %d: %d/2\n",cas++,q);

        else

            printf("Case %d: %d\n",cas++,q/2);

    }

    return 0;

}

巴特西

LightOJ 1029 【最小生成树】

最新文章

热门文章