开发者社区> 华山青竹> 正文

1078 最小生成树

简介: 链接:http://codevs.cn/problem/1078/ 题目描述 Description 农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。
+关注继续查看

链接:http://codevs.cn/problem/1078/

题目描述 Description

农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了使花费最少,他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。 每两个农场间的距离不会超过100000

输入描述 Input Description

第一行: 农场的个数,N(3<=N<=100)。

第二行..结尾: 接下来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上,他们是N行,每行由N个用空格分隔的数组成,实际上,他们每行限制在80个字符以内,因此,某些行会紧接着另一些行。当然,对角线将会是0,因为线路从第i个农场到它本身的距离在本题中没有意义。

输出描述 Output Description

只有一个输出,是连接到每个农场的光纤的最小长度和。

样例输入 Sample Input

4

0  4  9 21

4  0  8 17

9  8  0 16

21 17 16  0

样例输出 Sample Output

28

算法分析:

这道题是典型的最小生成树模板题。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define MAXV 100
 4 #define INF 100005
 5 void prim(int **edges,int n,int v);
 6 int main(int argc, char *argv[])
 7 {
 8     int N,**edges;
 9     int i,j;
10     scanf("%d",&N);
11     edges=(int **)malloc(sizeof(int*)*N);
12     for(i=0;i<N;i++)
13         edges[i]=(int *)malloc(sizeof(int)*N);
14     for(i=0;i<N;i++)
15         for(j=0;j<N;j++)
16             scanf("%d",&edges[i][j]);
17     prim(edges,N,0);
18     return 0;
19 }
20 void prim(int **edges,int n,int v)
21 {
22     int total=0;
23     int lowcost[MAXV];
24     // lowcost[k]=0标记k已经加入U.另外,lowcost[k]=w表示从最小生成树的点到达k节点的最短边是w 
25     int min;
26     int closest[MAXV],i,j,k;    //对于某个节点i∈V-U, closest[i]=v表示节点i借助某条边依附于处在U中的节点v。
27     for (i=0;i<n;i++)         //给lowcost[]和closest[]置初值
28     {    
29         lowcost[i]=edges[v][i];
30         closest[i]=v;           //closest[i]=v表示当前状态下到达i点的最合适的经过点是v 
31     }
32     for (i=1;i<n;i++)              //找出n-1个顶点
33     {
34         min=INF;
35         for (j=0;j<n;j++)       //在(V-U)中找出离U最近的顶点k
36             if (lowcost[j]!=0 && lowcost[j]<min) 
37             {
38                 min=lowcost[j];
39                 k=j;            //k记录最近顶点的编号
40             }
41         //printf(" 边(%d,%d)权为:%d\n",closest[k]+1,k+1,min);
42         total=total+min;
43         lowcost[k]=0;             //标记k已经加入U
44         for (j=0;j<n;j++)       //修改数组lowcost和closest
45             if (edges[k][j]!=0 && edges[k][j]<lowcost[j]) 
46             {
47                 lowcost[j]=edges[k][j];
48                 closest[j]=k; //closest[j]=k表示构造最小生成树过程中,当前状态下到达j节点最优的路径是经过k节点。
49             }
50     }
51     //printf("最小生成树权值之和:%d\n",total);
52     printf("%d\n",total);
53 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云进入Gartner云AI开发者服务挑战者象限
日前,国际权威研究机构Gartner发布2022年《云AI开发者服务魔力象限》。凭借达摩院领先的AI算法和阿里云丰富的产品体系,继2021年入围远见者象限之后,阿里云进一步跃升至挑战者象限,且成为报告中执行能力最强的中国企业。
15 0
机器学习之数据处理与可视化【鸢尾花数据分类|特征属性比较】
机器学习之数据处理与可视化【鸢尾花数据分类|特征属性比较】
6 0
线性回归算法之鸢尾花特征分类【机器学习】
线性回归算法之鸢尾花特征分类【机器学习】
8 0
支持向量机算法之鸢尾花特征分类【机器学习】
支持向量机算法之鸢尾花特征分类【机器学习】
4 0
朴素贝叶斯算法之鸢尾花特征分类【机器学习】【伯努利分布,多项式分布,高斯分布】
朴素贝叶斯算法之鸢尾花特征分类【机器学习】【伯努利分布,多项式分布,高斯分布】
3 0
每个开发人员都应该学习的 10 种算法
每个开发人员都应该学习的 10 种算法
7 0
开发指南—函数—日期时间函数
本文介绍了PolarDB-X支持的日期时间函数
3 0
如临现场的视觉感染力,NBA决赛直播还能这样看?
阿里云视频云联手百视TV,让NBA直播“降本又增效”
4 0
案例驱动 :从入门到掌握Shell编程详细指南
Shell是一个命令行解释器,接收应用程序用户命令,去调用操作系统的内核。它又是一种程序设计语言。作为命令语言,它交互式解释和执行用户输入的命令或者自动地解释和执行预先设定好的一连串的命令。它的特点是易编写、非常灵活。
4 0
使用Anaconda运行深度学习模型搭建训练测试
使用Anaconda运行深度学习模型搭建训练测试
4 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载