这是一个很简单的prime算法问题
在此！感谢我的数据结构赵老师，成功的把一个不喜欢写代码，疯狂想转专业的孩子爱上了算法，她能把一直觉得晦涩难懂的算法讲的很清晰明了
说回问题，给你n个村庄和一个二维矩阵，在这n个节点中修建出来一个高速公路，使得每个村庄都经过高速公路且高速公路的长度是最短的，并输出其中最大的边
其实就是无向图的最小生成树问题
AC代码：
/*
一个很简单的prime算法问题
*/
#include <stdio.h>
#include <stdlib.h>
#define N 501
int visit[N];
int distance[N][N];
void Init(int n)
{for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){scanf("%d",&distance[i][j]);}visit[i]=0;}return ;
}
int prime(int n)
{int maxn=-1;int lowcost[n+1],temp;int max=65537;for(int i=1;i<=n;i++){lowcost[i]=distance[1][i]; //初始化所有节点入树最短距离为到1节点的距离 }visit[1]=1; //1节点入树for(int i=2;i<=n;i++) //循环n-1次{max=65537;for(int j=1;j<=n;j++) //找出剩余节点中入树距离最小的{if(visit[j]==0&&lowcost[j]<max){max=lowcost[j];temp=j;}}if(max>maxn){maxn=max;}visit[temp]=1;for(int k=1;k<=n;k++){if(visit[k]==0&&lowcost[k]>distance[temp][k]){lowcost[k]=distance[temp][k];}}}return maxn;
}
int main()
{int T;scanf("%d",&T);while (T--){int n;scanf("%d",&n);Init(n);printf("%d\n",prime(n));}return 0;
}
//poj 2485