HDOJ1233 ( 还是畅通工程 ) 【最小生成树,kruscal】-阿里云开发者社区

开发者社区> 技术小哥哥> 正文

HDOJ1233 ( 还是畅通工程 ) 【最小生成树,kruscal】

简介:
+关注继续查看
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta 
复制代码
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 101
 6 typedef struct{
 7     int x,y;
 8     int len;
 9 }EDGE;
10 int map[N][N],set[N],n;
11 EDGE edge[N*N];
12 int cmp(const EDGE& a,EDGE& b)
13 {
14     return a.len<b.len;
15 }
16 int FindSet(int a)
17 {
18     return set[a];
19 }
20 void MergeSet(int a,int b)
21 {
22     int i;
23     for (i=1;i<=n;i++)
24         if(set[i]==a)
25             set[i]=b;
26 }
27 int main()
28 {
29     int i,p,sum,m,f,t;
30     while (scanf("%d",&n),n)//n为村庄个数
31     {
32         //初始化map
33         memset(map,0,sizeof(map));
34         //最多m条边
35         m=(n*(n-1))>>1;
36         //初始化set
37         for (i=1;i<=n;i++)    set[i]=i;    
38         //构建map
39         for (i=0;i<m;i++)    scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].len);
40         //已经选取的点的个数
41         p=0;
42         //路径总长度
43         sum=0;
44         //对边进行排序
45         sort(edge,edge+i,cmp);
46         for (i=0;i<m&&p!=n;i++)
47         {
48             //查找当前边的起始点是否在同一个集合中
49             f=FindSet(edge[i].x);
50             t=FindSet(edge[i].y);
51             if(f!=t)
52             {
53                 MergeSet(f,t);
54                 p++;
55                 sum+=edge[i].len;
56             }
57         }
58         printf("%d\n",sum);
59     }
60     return 0;
61 }
复制代码

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/05/12/2497640.html,如需转载请自行联系原作者

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

相关文章
python应用领域分析
python应用领域分析
5 0
安卓平板体验Java开发,还能白嫖一年阿里无影云!真香
阿里无影云早有耳闻,前两天看朋友发体验照片,可能是程序员天生爱折腾的特性又发挥作用了,自己也没能忍住,赶快下载体验了一把,没想到“很香”。我体验了浏览器端、Windows 客户端和安卓平板端,下面就来聊聊使用的过程和使用体验。内含一年免费无影云的白嫖方法,千万别错过哦~
34 0
styleGAN环境搭建 、 动漫模型效果测评
styleGAN环境搭建 、 动漫模型效果测评
5 0
数据类型-数值和字符串 | 学习笔记
快速学习数据类型-数值和字符串。
5 0
简单实用的redis分布式锁
简单实用的redis分布式锁
3 0
Linux 基本操作 | 学习笔记
快速学习 Linux 基本操作。
11 0
使用 Go 语言编写的恶意软件激增 2000%
  近日,网络安全公司 Intezer 发布了 2022 年基于 Go 语言恶意软件的报告。报告指出:恶意软件的开发者已经从 C 和 C++ 逐渐转向 Go 语言,自 2017 年以来,基于 Go 语言的恶意软件数量呈现爆发式增长,增幅超过了 2000%。   自从 2012 年发现了第一个使用 Go 语言编写的恶意软件之后,Go 语言就在恶意软件领域渐渐流行起来了。2019 年 7 月,Palo Alto Networks 发布了一份使用 Go 语言编写的恶意软件分析报告。报告发现,2019 年以前使用 Go 语言编写恶意软件是一件罕见的事情,但到了 2019 年,这种情况每天都会发生,2
6 0
ECS使用体验
云服务器(ECS),是一种简单高效,处理能力可以弹性伸缩的计算服务。
7 0
Java classloader详解
Java程序并不是一个可执行文件,而是由很多的Java类组成,其运行是由JVM来控制的。而JVM从内存中查找到类,而真正将类加载进内存的就是ClassLoader,可以说我们每天都在接触ClassLoader,但是很多时候我们没有明白其执行的流程和原理。
8 0
QT和MFC的优缺点比较
QT和MFC的优缺点比较
5 0
2010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载