巢穴

about:blank

P1258

同刚才的题.....
刚才的代码连改都不怎么用改..
裸prim..

#include <iostream>
using namespace std;

const int MAXN=101;
const int INF=0x7fffffff;
int n;
int edge[MAXN][MAXN];
bool hash[MAXN];
int dist[MAXN];
void prim()
{
     memset(hash,0,sizeof(hash));
     for (int i=0;i<n;i++)
         dist[i]=INF;
     dist[0]=0;
     int ans=0;
     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;}
         }
         ans+=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<<ans<<endl;
    // system("pause");
}

int main()
{
    while(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:44 Vincent 阅读(81) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


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