/*kruskal算法*/
#include <iostream>
//#include <fstream>
#include <algorithm>
using namespace std;
/*708K 922MS*/
typedef struct _edge
{
int x,y;
int w;
}edge; int n;
int num;
//fstream fin; void kruskal(edge *e,int len);
int cmp(const void *a,const void *b); int main()
{
//fin.open("2485.txt",ios::in);
int t;
cin>>t;
while(t--)
{
cin>>n;
edge *e=new edge[n*n];
int temp;
int len=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>temp;
if(temp)
{
e[len].x=i;
e[len].y=j;
e[len++].w=temp;
}
}
kruskal(e,len);
cout<<num<<endl;
delete []e;
}
system("pause");
return 0;
} int cmp(const void *a,const void * b)
{
edge *a1=(edge *)a;
edge *b1=(edge *)b;
return a1->w-b1->w;
} void kruskal(edge *e,int len)
{
qsort(e,len,sizeof(edge),cmp);
int *s=new int[n];
memset(s,0,sizeof(int)*n);
int parts=0;
int max,u,v; for(int i=0;i<len;i++)
{
u=e[i].x; v=e[i].y;
if(!s[u]&&!s[v])
{
parts++;
s[u]=parts;
s[v]=parts;
max=e[i].w;
}
else if(s[u]&&!s[v])
{
s[v]=s[u];
max=e[i].w;
}
else if(s[v]&&!s[u])
{
s[u]=s[v];
max=e[i].w;
}
else
{
if(s[v]!=s[u])
{
int temp1=s[u];
int temp2=s[v];
if(temp1>temp2)
{
temp1=s[v];
temp2=s[u];
}
//更新
for(int j=0;j<n;j++)
{
if(s[j]==temp2)
s[j]=temp1;
else if(s[j]>temp2)
s[j]--;
}
max=e[i].w;
}
}
} num=max;
}
这时间 估计倒数了！