最小生成树，并查集的思想 nyoj1239

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int n,pre[10010],cnt;

struct node

{

    int x,y;

    int val;

} p[10010];

void init()

{

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

        pre[i]=i;

}

int cmp(node s1,node s2)

{

    return s1.val<s2.val;

}

int find(int x)

{

    return x==pre[x]?x:find(pre[x]);

}

int join(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx!=fy)

    {

        pre[fx]=fy;

        return 1;

    }

    return 0;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        init();

        cnt=0;

        scanf("%d",&n);

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

        {

            for(int j=1; j<=n; j++)

            {

                scanf("%d",&p[cnt].val);

                p[cnt].x=i,p[cnt++].y=j;

            }

        }

        sort(p,p+cnt,cmp);

        int sum=0;

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

        {

            if(join(p[i].x,p[i].y))

                sum+=p[i].val;

        }

        printf("%d\n",sum);

    }

    return 0;

}

巴特西

最小生成树，并查集的思想 nyoj1239

最新文章

热门文章