#include<iostream>
#include<cstdlib>
using namespace std;
int n,k;
struct edge
{
    int u;
    int v;
    int w;
};
edge p[500*500];

int cmp(const void *a,const void *b)
{
    edge *p1=(edge *)a;
    edge *p2=(edge *)b;
    return p1->w-p2->w;
}

void kruskal()
{
    int flag[500];
    for(int i=1;i<=n;i++)
        flag[i]=i;
    qsort(p,k,sizeof(edge),cmp);
    int maxn=0;
    for(int i=1;i<=k;i++)
    {
        if(flag[p[i].u]!=flag[p[i].v])
        {
            int t=flag[p[i].u];
            for(int j=1;j<=n;j++)
                if(flag[j]==t) flag[j]=flag[p[i].v];
            if(p[i].w>maxn) maxn=p[i].w;

            //cout<<i<<' '<<maxn<<endl;
        }
    }
    cout<<maxn<<endl;
}


int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        cin>>n;
        k=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
        {
            k++;
            p[k].u=i;
            p[k].v=j;
            cin>>p[k].w;
        }
        kruskal();
    }
}

• Re:第一次krustal，一次A，留代码做纪念 (1169) MikuGhoul 2016-08-27 16:40:30