第一道Kruskal算法题

 

 

 

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

#define max 505

int f[max],maxw;

struct edge{

    int st,en,w;

}ed[max*max/2];

int  find(int k){

    if(k!=f[k])f[k]=find(f[k]);

    return f[k];

}

void combine(int a,int b,int w){

    if(a==b)return;

    if(a>b){f[a]=b;}

    if(b>a){f[b]=a;}

    maxw=w;

}

bool cmp(edge a,edge b){

    return a.w<b.w;

}

void Kruskal(int l){

    for(int i=0;i<l;i++){

        combine(find(ed[i].st),find(ed[i].en),ed[i].w);

    }

}

int main(){

    int t,k,n,b;

    //freopen("test.txt","r",stdin);

    cin>>t;

    while(t--){

        b=0;

        cin>>n;

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

            f[i]=i;

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

                cin>>k;

                if(j>i){ed[b].st=i;ed[b].en=j;ed[b++].w=k;}

            }

        }

        sort(ed,ed+b,cmp);

        Kruskal(b);

        cout<<maxw<<endl;

    }

    return 0;

}