题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=362#problem/B
这题思路和上题一样,也用prim,代码如下:
#include <stdio.h>
#include <string.h>
int inf=101;//常量表示无穷
int sum;
int map[51][51];//数组存储各边的关系
int visit[51];//标记是否纳入集合
void prime(int n)//prim的实现
{
 int min,rec,j,i;
 for(i=1;i<=n;i++)
  visit[i]=0;//初始化
 visit[1]=1;//默认的第一个标记
 for(i=1;i<n;i++)
 {
  min=inf;
  for( j=1;j<=n;j++)
  {     
   
   if(!visit[j]&&map[1][j]<min)
   {
    min=map[1][j];
    rec=j;
   }
  }
  sum+=min;
  visit[rec]=1;//标记已选
  for(j=1;j<=n;j++)//比较关键的一部处理,体现prim过程
  {  
   
   if(!visit[j]&&map[1][j]>map[rec][j])
   {
    map[1][j]=map[rec][j];
   }
  }
 }
}
int main()
{
    int n,m,dis,i,j,tv,td;
 while(scanf("%d%d",&n,&m),n)
 {
  sum=0;
  for(i=1;i<=n;i++)
            for(j=1;j<=n;j++) 初始化存储边的数组
            {
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=inf;
            }
   for(i=0;i<m;i++)
   {
    scanf("%d%d%d",&tv,&td,&dis);//输入数据
    if(dis<map[tv][td])
    {
     map[tv][td]=dis;
     if(map[tv][td]>map[td][tv])  //问题简化
      map[tv][td]=map[td][tv];
     else
      map[td][tv]=map[tv][td];
    }
   }
   if(m!=0)
    prime(n);
   printf("%d\n",sum);
 }
 return 0;
}

发表评论

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

Post Navigation