学步园

#include <cstdio>

#include <algorithm>

const int MAXNODE = 505 , inf=65538;   //MAXNODE 邻接矩阵的大小  inf 根据题目数据定义为无穷大。

using namespace std;

int Graph[MAXNODE][MAXNODE];

int MinSpace[MAXNODE];              //将最小生成树的所有边全值存在MinSpace数组中。

int n,m;

int main()
{
    void Creat_Graph();
    void prim();
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        Creat_Graph();
        prim();
        sort(MinSpace,MinSpace+m-1);        //用sort函数按照升序对MinSpace中的数据进行排序。
        printf("%d\n",MinSpace[m-2]);       //输出MinSpace中最大的值
    }
    return 0;
}

void Creat_Graph()                        //邻接矩阵的形式存储图。
{
    for(int i = 0 ; i < m ; i++ )
    {
        for( int j = 0 ; j < m ; j++ )
        {
            scanf("%d",&Graph[i][j]);
        }
    }

}

void prim()
{
    int key=0,k;
    int LowCost[MAXNODE];
    int MinCost,CloseVertex[MAXNODE];
    for(int i = 0 ; i< m ; i++)
    {
        LowCost[i]=Graph[0][i];    //LowCost数组中存储到其他顶点的最短距离。
        CloseVertex[i]=0;    //CloseVerterx中存放最小生成树的顶点。closeVertex[i]==0 表示该顶点存入最小生成树中。
    }
    for(int i = 1 ; i < m ; i++ )
    {
        MinCost=inf;
        for(int j = 0 ; j < m ; j++)
        {
            if(LowCost[j] < MinCost && LowCost[j]!=0)
            {
                MinCost=LowCost[j];     //LowCost[j]==0,表示j顶点存入最小生成树中。
                k=j;
            }
        }
       MinSpace[key++]=MinCost;    //将依次得到的最短距离存入MinSpace数组。
        LowCost[k]=0;
        for(int j = 0 ;j < m ; j++ )
        {
            if(Graph[k][j]<LowCost[j]  && LowCost[j])   //修改其他顶点的边的权值跟最小生成树的顶点序号。
            {
                LowCost[j]=Graph[k][j];
                CloseVertex[j]=k;
            }
        }
    }
}