巢穴

about:blank

P2485

poj恢复的好快..
prim..然后求出最长的边..

#include <iostream>
using namespace std;

const int MAXN=501;
int t;
int n;
int edge[MAXN][MAXN];
int dist[MAXN];
bool hash[MAXN];
const int INF=65537;
void prim()
{
     memset(hash,0,sizeof(hash));
     for (int i=0;i<n;i++)
         dist[i]=INF;
     dist[0]=0;
     int max=-1;
     for (int i=0;i<n;i++)
     {
         
         int u=-1;
         int min=INF;
         for (int j=0;j<n;j++)
         {
             if (hash[j]) continue;
             if (min>dist[j]) {min=dist[j];u=j;}
         }
         if (max<dist[u]) max=dist[u];
       //  cout<<dist[u]<<endl;
         hash[u]=true;
         for (int j=0;j<n;j++)
         {
             if (dist[j]>edge[u][j]) dist[j]=edge[u][j];
         }
     }
     cout<<max<<endl;
    // system("pause");
}
int main()
{
 cin>>t;
 while(t--)
 {
  cin>>n;
  for (int i=0;i<n;i++)
   for (int j=0;j<n;j++)
   {
    cin>>edge[i][j];
   }
  prim();
 }
 return 0;
}

posted on 2009-10-06 16:32 Vincent 阅读(49) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理