TOJ–3073:Country Road 最小生成树(Prim)

不管现实多么惨不忍睹,都要持之以恒地相信,这只是黎明前短暂的黑暗而已。不要惶恐眼前的难关迈不过去,不要担心此刻的付出没有回报,别再花时间等待天降好运。真诚做人,努力做事!你想要的,岁月都会给你。TOJ–3073:Country Road 最小生成树(Prim),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

题目源地址:http://acm.tju.edu.cn/toj/showp.php?pid=3073

AC代码:

//TOJ--3073:Country Road     最小生成树(Prim) 
#include<iostream>
#include<memory.h>
#define MAX 1003
#define INF 1010
using namespace std;

int map[MAX][MAX],visited[MAX];
int dist[MAX];
int N,M,K;

int Prim()
{
    int i,j,pos,min,sum;
    
    for(i=1;i<=N;i++)
       dist[i]=map[1][i];//dist[]初始化为从起点到各点的距离。
       
    visited[1]=1;
    
    for(i=1;i<N;i++)//总共N个节点,已经把第一个节点放进去了,剩下还得放N-1个节点 
    {
        min=INF;
        for(j=1;j<=N;j++)
        {
           if(!visited[j] && dist[j]<min)//找与刚加入的点距离最小的点
           {
              min=dist[j];
              pos=j;
           }
        }
        
        visited[pos]=1;//将pos点加入 
        
        for(j=1;j<=N;j++)//更新dist[]
        {
           if(!visited[j] && map[pos][j]<dist[j])
           {
              dist[j]=map[pos][j];
           }
        }
    }
    
    sum=0;
    for(i=1;i<=N;i++)
    {
       sum=sum+dist[i];
       if(dist[i]==INF)
          return -1;
    }
    return sum;
}

int main()
{
    int caseNum;
    int i,j,s,t,d;
    cin>>caseNum;
    while(caseNum--)
    {
       cin>>N>>M>>K;
       memset(visited,0,sizeof(visited));
       
       for(i=1;i<=N;i++)//初始化map
       {
          for(j=1;j<=N;j++)
          {
             if(i==j)   map[i][j]=0;//节点到自身的距离设为0
             else       map[i][j]=INF;//节点到其他节点的距离设为一个比较大的值(改值要比所有节点间最大权值大) 
          }
       }
       
       for(i=1;i<=M;i++)
       {
          cin>>s>>t;
          map[s][t]=0;//输入已经有路径的节点对,并将有路径可达的节点间距离设为0 
          map[t][s]=0;//注意:无向图,双向赋值
       }
       
       for(i=1;i<=K;i++)
       {
          cin>>s>>t>>d;
          map[s][t]=d;//若在节点s和t间修路,则距离为d 
          map[t][s]=d;
       }
       cout<<Prim()<<endl;
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/163060.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!