/*
 * Author: kymo
 * Created Time:  2011/7/21 10:33:06
 * File Name: 2485-cruskal.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define F(a,b) for(int i = a;i <= b;i ++)
#define int_max 99999999999LL
#define eps 1.0e-6
#define max 250001
struct node{
    int u,v;
    int val;
    bool operator<(const node &a)const{
       return a.val > val;
    }
}Node[max];
int root[501];
int n,e,T;
int find(int n){
    if(n != root[n]) root[n] = find(root[n]);
    return root[n];
}
int cruskal(){
    int count = 0;
    for(int j = 0;j <= n-1;j ++) root[j] = j;
    stable_sort(Node,Node + e);
    for(int j = 0;j <= e-1;j ++){
        int t1 = find(Node[j].u);
        int t2 = find(Node[j].v);
        if(t1 != t2){
            root[t2] = t1;
            if(count <= Node[j].val) count = Node[j].val;
        }
    }
    return count;
}
int A;
int main() {
    scanf("%d",&T);
    for(int j = 0;j <= T-1;j ++){
//        cin>>n;
        scanf("%d",&n);
        e = 0;
        for(int k = 0;k <= n-1;k ++){
            for(int l = 0;l <= n-1;l ++){
                //cin>>A;
                scanf("%d",&A);
                if(A!=0){
                    Node[e].u = k;
                    Node[e].v = l;
                    Node[e].val = A;
                    e ++;
                }
            }
        }
        cout<<cruskal()<<endl;
    }
    return 0;
}



/*
 * Author: kymo
 * Created Time:  2011/7/21 10:00:19
 * File Name: 7-21-1.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define F(a,b) for(int i = a;i <= b;i ++)
#define int_max 99999999999LL
#define eps 1.0e-6
#define max 501

#define inf 32544
int g[max][max];
int visited[max];
int cost[max];
int e,n,T;
void prime(int v){
    for(int j = 0;j <= n-1;j ++){
        cost[j] = g[v][j];
        visited[j] = 0;
    }
    visited[v] = 1;
    for(int l = 0;l <= n-2;l ++){
        int max_num = inf;
        int tp;
        for(int k = 0;k <= n-1;k ++){
            if(max_num >= cost[k]&&!visited[k]){
                max_num = cost[k];
                tp = k;
            }
        }
        visited[tp] = 1;
        for(int j = 0;j <= n-1;j ++){
            if(!visited[j]&&cost[j] > g[tp][j]){
                cost[j] = g[tp][j];
            }
        }
    }
}
    
        
int main() {
    scanf("%d",&T);
    for(int j = 0;j <= T-1;j ++){
        scanf("%d",&n);
        e = 2*n*(n-1);
        for(int i = 0;i <= n-1;i ++){
            for(int l = 0;l <= n-1;l ++){
                scanf("%d",&g[i][l]);
            }
        }
        prime(0);
    
        int s = 0;
        for(int j = 0;j <= n-1;j ++){
            if(s < cost[j]) s = cost[j];
        }
        printf("%d\n",s);
    }
    return 0;
}

• Re:我是来看楼主的“cruskal”的，是Kruskal阿 少年。 (5) liaoxinghao 2011-07-24 16:09:23