题目传送门

//题意：本题要求图中最小生成树的最长边
//解题思路：直接在prim算法找最小边的过程中维护最小值

//Created Author: just_sort
//Created Time : 2016/1/16 17:45
//File Name : HighWays
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Read(x) scanf("%d",&x)
#define INF 0x3f3f3f3f
int maze[505][505],dis[505];
bool vis[505];
int n;
int Prim()
{
    int ans=0;
    dis[1]=0;
    for(int i=1;i<=n;i++)
    {
        int mark,minn=INF;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<minn)
            {
                minn=dis[j],mark=j;
            }
        }
        vis[mark]=true;
        ans=max(ans,dis[mark]);
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]>maze[mark][j])
                dis[j]=maze[mark][j];
        }
    }
    return ans;
}
int main()
{
    int tt;
    Read(tt);
    while(tt--)
    {
        Read(n);
        memset(maze,INF,sizeof(maze));
        memset(vis,false,sizeof(vis));
        memset(dis,INF,sizeof(dis));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                Read(maze[i][j]);
        //for(int i=1;i<=n;i++)maze[i][i]=INF;
        int ans=Prim();
        printf("%d\n",ans);
    }
    return 0;
}