POJ2485Highways

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

题意 ： 这道题和1258很像，但是这道题求的是最小生成树中最大的那条边，所以在函数里处理一下就行了。

思路 ： 赤裸裸的最小生成树啊，但是这道题一定要注意，因为底下有提醒，一定要用scanf输入，结果我就很悲剧的没看到啊，然后一直改一直改，到最后又去看了一遍题才发现要用scanf啊，╮(╯▽╰)╭

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int ans,dis[][];

 const int INF = << ;

 int vis[],n,low[];

 int prim()

 {

     memset(vis,,sizeof(vis));

     int i,j,flag,min;

     ans =  ;

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

     {

         low[i] = dis[][i];

     }

     //low[1] = 0;

     vis[] =  ;

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

     {

         min = INF;

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

         {

             if(min > low[j]&&!vis[j])

             {

                 min = low[j] ;

                 flag = j;

             }

         }

         /*if(min >= INF)

         {

             flag = -1 ;

             break ;

         }*/

         if(ans < min)

         ans = min ;

         //ans+=min ;

         vis[flag] =  ;

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

         {

             if(dis[flag][j] < low[j] && !vis[j])

             low[j] = dis[flag][j];

         }

     }

     return ans ;

 }

 int main()

 {

     int s;

     scanf("%d",&s);

     while(s--)

     {

         scanf("%d",&n);

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

         {

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

             {

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

             }

         }

         ans = prim();

         cout<<ans<<endl;

     }

     return  ;

 }