无声的月

 

POJ 1251 最小生成树 prim

 

#include<iostream>
using namespace std;
const int MAXV=30;
const int INF=1000;
int cost[MAXV][MAXV],n,v;
int Prim(int cost[][MAXV],int n,int v)
{
    int lowcost[MAXV],min1;
    int closest[MAXV],i,j,k,sum;
  
    sum=0;
    for(i=0;i<n;i++)
    {
        lowcost[i]=cost[v][i];
        closest[i]=v;
    }
    
    lowcost[0]=0;
    for(i=1;i<n;i++)
    {
        min1=INF;
        for(j=0;j<n;j++)
        {
            if(lowcost[j]!=0&&lowcost[j]<min1)
            {
                min1=lowcost[j];
                k=j;
            }
        }
        sum+=min1;
        lowcost[k]=0;
        for(j=0;j<n;j++)
        {
            if(cost[k][j]!=0&&cost[k][j]<lowcost[j])
            {
                lowcost[j]=cost[k][j];
                closest[j]=k;
            }
        }
    }
    return sum;
}
int main()
{
    int i,j,n,u,v,k,w;
    char ch;
    while(cin>>n,n)
    {
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        cost[i][j]=INF;
        for(j=0;j<n-1;j++)
        {
           cin>>ch;
           u=ch-'A';
           cin>>k;
           for(i=0;i<k;i++)
           {
              cin>>ch;
              v=ch-'A';
              cin>>w;
              cost[u][v]=w;
              cost[v][u]=w;
            }
        }
        cout<<Prim(cost,n,0)<<endl;
    }
}

posted on 2010-07-23 15:10 Baron 阅读(138) 评论(0)  编辑 收藏 引用


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


导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜