Highways(prim)

http://poj.org/problem?id=2485

此题是求最小生成树里的最大权值。prim算法：

 #include<stdio.h>

 #include<string.h>

 const int maxn=;

 const int INF = <<;

 int map[maxn][maxn];

 int dis[maxn],vis[maxn];

 int n,maxm;

 void prim()

 {

     int pos;

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

     {

         dis[i] = map[][i];

     }

     vis[] = ;

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

     {

         int min = INF;

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

         {

             if (!vis[j] && dis[j] < min)

             {

                 min = dis[j];

                 pos = j;

             }

         }

         if(min > maxm)

         {

             maxm = min;

         }

         vis[pos] = ;

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

         {

             if (!vis[j] && dis[j] > map[pos][j])

                 dis[j] = map[pos][j];

         }

     }

 }

 void init()

 {

     maxm = -;

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

     {

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

         {

             map[i][j] = INF;

         }

         map[i][i] = ;

         vis[i] = ;

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         init();

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

         {

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

             {

                 scanf("%d",&map[i][j]);

             }

         }

         prim();

         printf("%d\n",maxm);

     }

     return ;

 }