题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=362#problem/A
一开始想用KrusKal做,但是好长时间没弄出来,后来换了Prim,思路变得就比较容易了,详细代码如下:
#include <stdio.h>
#include <string.h>
int inf=100001;//代表无穷
int sum;
int map[30][30];数组存储各边的关系
int visit[30];标记是否纳入集合
void prime(int n)prim的实现
{
 int min,rec,j,i;
 for(i=0;i<=n;i++)
  visit[i]=0;初始化
  visit[0]=1;//默认的第一个标记
 for(i=1;i<n;i++)
 {
  min=inf;
  for( j=0;j<n;j++)
  {
   if(!visit[j]&&map[0][j]<min)
   {
    min=map[0][j];
    rec=j;
   }
  }
  sum+=min;
  visit[rec]=1;//标记已选
  for(j=0;j<n;j++)//比较关键的一部处理,体现prim过程
  {
    if(!visit[j]&&map[0][j]>map[rec][j])
    {
    map[0][j]=map[rec][j];
    }
  }
 }
}
int main()
{
    int n,m,dis,i,j;
    char s1,s2;
    while(scanf("%d",&n),n)
    {
        sum=0;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=inf;
            }
   for(i=0;i<n-1;i++)
   {
    getchar();
    scanf("%c%d",&s1,&m);
    for(j=0;j<m;j++)
    {
     getchar();
     scanf("%c%d",&s2,&dis);
     map[s1-'A'][s2-'A']=map[s2-'A'][s1-'A']=dis;//要理解,技巧
    }
   }
   prime(n);
   printf("%d\n",sum);
    }
 return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation