Kruskal算法求最小生成树(POJ2485)

题目链接：http://poj.org/problem?id=2485

#include <iostream>

#include <stdio.h>

#include <memory.h>

#include <string.h>

#include <stdlib.h>

using namespace std;

#define inf 100000000

#define N 505

#define M N*N

struct note {

    int u,v;

    int c;

    note() {}

    note(int u,int v,int c):u(u),v(v),c(c) {}

} p[M];

int e,n,m;

int father[N];      ///表示x的父亲的编号

void addnote(int u,int v,int c) {

    p[e++]=note(u,v,c);

}

int cmp(const void *a,const void *b) {

    note *aa=(note *)a;

    note *bb=(note *)b;

    return aa->c-bb->c;

}

///初始化每个节点的祖先，即为独立的点

void set_clear() {

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

        father[i]=i;

}

///找到x的祖先。

int find(int x) {

    if(x!=father[x])

        father[x]=find(father[x]);

    return father[x];

}

int kruskal(int n) {

    set_clear();

    int m=;        ///只要找n-1条边，就把图构成了

    int ans=;

    for(int i=; i<e; i++) {

        int x=find(p[i].u);

        int y=find(p[i].v);

        if(x==y) continue;

        m++;

        ans=p[i].c;

        father[y]=x;        ///father[y]的祖先改为x;合并两个不相交的集合

        if(m==n-) break;

    }

    if(m<n-) return -;

    else return ans;

}

int main() {

    int T;

    scanf("%d",&T);

    while(T--) {

        scanf("%d",&n);

        e=;        ///边的个数

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

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

                int c;

                scanf("%d",&c);

                addnote(i,j,c);

            }

        }

        qsort(p,e,sizeof(p[]),cmp);

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

    }

    return ;

}