POJ - 2485 Highways（最小生成树，最长边，Prim算法）

POJ - 2485

让求出最小生成树里面的最长的边，Prim算法走一遍即可

#include<cstdio>
#include<cstring>
const int N = 510, INF = 1e9;
int e[N][N],dis[N],vis[N];
int n;
void Prim()
{
    memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) dis[i]=e[1][i];vis[1]=1;dis[1]=0;int ans=0;for(int i=1;i<=n-1;i++) {
    int minn=INF,u;for(int j=1;j<=n;j++) {
    if(!vis[j]&&minn>dis[j]) {
    minn=dis[j];u=j;}} vis[u]=1;if(ans<minn) ans=minn;for(int j=1;j<=n;j++) {
    if(!vis[j]&&dis[j]>e[u][j])dis[j]=e[u][j];}}printf("%d\n",ans);
} 
int main()
{
    int t;scanf("%d",&t);while(t--) {
    memset(e,0x3f,sizeof(e));scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&e[i][j]);Prim();        }return 0;
}