zoj 3204 Connect them kruskal

 kruskal模板题

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX 102
using namespace std;

struct edge
{
    int x,y,w;
    edge(int x=0,int y=0,int w=0):x(x),y(y),w(w) {}
} e[MAX*MAX];
struct node
{
    int x,y;
} pp[MAX*MAX];

int T,n,num,ppnum;
int fa[MAX];


int getfather(int x)
{
    if(x==fa[x])return x;
    else return fa[x]=getfather(fa[x]);
}

int cmp(struct edge aaa,struct edge bbb)
{
    if(aaa.w==bbb.w){
        if(aaa.x==bbb.x) return aaa.y<bbb.y;
        else return aaa.x<bbb.x;
    }
    else return aaa.w<bbb.w;
}
int cmp1(struct node aa,struct node bb)
{
    if(aa.x==bb.x) return aa.y<bb.y;
    else return aa.x<bb.x;
}
void kruscal()
{
    int i;
    sort(e,e+num,cmp);
    int cnt=n;
    for(i=1; i<=n; i++)fa[i]=i;
    for(i=0; i<num; i++)
    {
        int t1=getfather(e[i].x);
        int t2=getfather(e[i].y);
        if(t1!=t2)
        {
            pp[ppnum].x=e[i].x;
            pp[ppnum].y=e[i].y;
            ppnum++;
            fa[t1]=t2;
            cnt--;
            if(cnt==1)break;
        }
    }
    if(cnt>1) {printf("-1\n");ppnum=0;}
}

int main()
{
    int i,j;
    int a[102][102];
    scanf("%d",&T);
    while(T--)
    {
        num=0;
        scanf("%d",&n);
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                scanf("%d",&a[i][j]);
        for(i=1; i<n; i++)
            for(j=i+1; j<=n; j++)
            if(a[i][j]>0)
            {
                e[num].x=i;
                e[num].y=j;
                e[num].w=a[i][j];
                num++;
            }
        ppnum=0;
        kruscal();
        sort(pp,pp+ppnum,cmp1);
        for(i=0;i<ppnum;i++){
            if(i!=ppnum-1){
                printf("%d %d ",pp[i].x,pp[i].y);
            }
            else printf("%d %d\n",pp[i].x,pp[i].y);
        }
    }
    return 0;
}

zoj 3204 Connect them kruskal

原文：http://blog.csdn.net/cnh294141800/article/details/19924683