poj 2485 求最小生成树中 最长的一条边

Sample Input

1 //T

3 //n
0 990 692 //邻接矩阵
990 0 179
692 179 0
Sample Output

692

prim

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <cmath>

 # define LL long long

 using namespace std ;

 const int INF=0x3f3f3f3f;

 const int MAXN=;

 bool vis[MAXN];

 int lowc[MAXN];

 int n ;

 int cost[MAXN][MAXN] ;

 int MAX =  ;

 int Prim()//点是0~n-1

 {

     int ans=;

     memset(vis,false,sizeof(vis));

     vis[]=true;

     for(int i=;i<n;i++)lowc[i]=cost[][i];

     for(int i=;i<n;i++)

     {

         int minc=INF;

         int p=-;

         for(int j=;j<n;j++)

             if(!vis[j]&&minc>lowc[j])

             {

                 minc=lowc[j];

                 p=j;

             }

             if(minc==INF)return -;//原图不连通

             ans+=minc;

             if (minc > MAX)

                 MAX = minc ;

             vis[p]=true;

             for(int j=;j<n;j++)

                 if(!vis[j]&&lowc[j]>cost[p][j])

                     lowc[j]=cost[p][j];

     }

     return ans;

 }

 int main()

 {

    // freopen("in.txt","r",stdin) ;

     int T ;

     cin>>T ;

     while(T--)

     {

         cin>>n ;

         int w ;

         int i , j ;

         for (i =  ; i < n ; i++)

             for (j =  ; j < n ; j++)

                {

                    cin>>w ;

                    if(w==)

                      cost[i][j] = INF ;

                    else

                      cost[i][j] = w ;

                }

         MAX =  ;

         Prim() ;

         cout<<MAX<<endl ;

     }

     return  ;

 }