POJ2485

poj2485.cpp

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <fstream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#define MAX(a,b) (a>b?a:b)
#define sd(x) scanf("%d",&x)
#define sdd(a,b) scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define slflf(x,y) scanf("%lf%lf",&x,&y)
#define abs(x) (x<0?(-x):x)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;

const int dsj_lenth = 505;

int dsj[dsj_lenth];
int graph[dsj_lenth][dsj_lenth];
bool isUsed[dsj_lenth*dsj_lenth];

void init()
{
    for (int i=0; i<dsj_lenth; i++) dsj[i]=i;
    memset(isUsed,0,sizeof(isUsed));
}

int Find(int x)
{
    return dsj[x]==x?x:dsj[x]=Find(dsj[x]);
}

inline void Union(int a,int b)
{
    dsj[a]=b;
}


struct road
{
    int u,v,w;
} r[dsj_lenth*dsj_lenth];

bool cmp(road a,road b)
{
    return a.w<b.w;
}


int main()
{
    int t;sd(t);
    while(t--)
    {
        init();
        int n;sd(n);
        int cnt=0;
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<n;j++)
            {
                sd(graph[i][j]);
                if (i>j)
                {
                    r[cnt].u = i;
                    r[cnt].v = j;
                    r[cnt++].w = graph[i][j];
                }
            }
        }
        sort(r,r+cnt,cmp);
        int built=0;
        for (int i=0;i<cnt;i++)
        {
            int fa = Find(r[i].u),fb = Find(r[i].v);
            if (fa!=fb)
            {
                built++;
                Union(fa,fb);
                isUsed[i]=1;
            }
            if (built==n-1) break;
        }
        int ans=0;
        for (int i=0;i<cnt;i++)
        {
            if (isUsed[i] && ans < r[i].w)
            {
                ans=r[i].w;
            }
        }
        cout << ans << endl;
    }
    return 0;
}