//poj 2485 还是先用prime,写起来比较快 题意是问最小生成树的最大边 #include <iostream> #include <algorithm> #define inf 65537 using namespace std; int weight[501][501]; int dist[501]; bool mark[501]; int max1; int prime(int n) { dist[0] = 0; mark[0] = true; for(int i =1; i < n; i++) { dist[i] = weight[0][i]; } for(int i = 1; i < n; i++) { int min1 = inf; int minIndex = -1; for(int j = 1; j < n; j++) { if(!mark[j] && dist[j] < min1) { min1 = dist[j]; minIndex = j; } } if(min1 > max1) max1 = min1; dist[minIndex] = 0; mark[minIndex] = true; for(int j = 1; j < n; j++) if(!mark[j]) dist[j] = (weight[minIndex][j] < dist[j])?weight[minIndex][j]:dist[j]; } return max1; } int main() { int t; cin>>t; while(t--) { memset(weight, 0, sizeof(weight)); memset(dist, 0, sizeof(dist)); memset(mark, 0, sizeof(mark)); int n; cin>>n; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin>>weight[i][j]; } } max1 = 0; cout<<prime(n)<<endl; } return 0; }