还是畅通工程(MST,不存在得不到MST的情况)

2024-02-20 22:32

本文主要是介绍还是畅通工程(MST,不存在得不到MST的情况),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 53511    Accepted Submission(s): 24304
Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最小的公路总长度。
Sample Input
 
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
 
3
5

注意:该例不存在得不到最小生成树的情况,所以最后我们并没有对所有节点是否属于同一个集合进行判断。若可能出现此情况,则该步不能省略。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define N 1000
int Tree[N];
struct edge{int a,b;int cost ;bool operator< (const edge &A)const{return cost<A.cost;}
}edge[6000];
int findroot(int x)//查找根节点
{if(Tree[x]==-1)return x;else{int tmp=findroot(Tree[x]);Tree[x]=tmp;return tmp;}
}
int main()
{int n,m,i,j;while(~scanf("%d",&n)&&n!=0){ m=n*(n-1)/2;for( i=1;i<=m;i++){scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);}sort(edge+1,edge+1+m);for(i=1;i<=n;i++)Tree[i]=-1;//初始时所有节点都属于孤立的集合int ans=0; int a,b;for( i=1;i<=m;i++){a=findroot(edge[i].a);b=findroot(edge[i].b);if(a!=b){Tree[a]=b;ans+=edge[i].cost;//累计该边权值}} printf("%d\n",ans );  }return 0;
}

这篇关于还是畅通工程(MST,不存在得不到MST的情况)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/729733

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

easyui同时验证账户格式和ajax是否存在

accountName: {validator: function (value, param) {if (!/^[a-zA-Z][a-zA-Z0-9_]{3,15}$/i.test(value)) {$.fn.validatebox.defaults.rules.accountName.message = '账户名称不合法(字母开头,允许4-16字节,允许字母数字下划线)';return fal

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Jenkins构建Maven聚合工程,指定构建子模块

一、设置单独编译构建子模块 配置: 1、Root POM指向父pom.xml 2、Goals and options指定构建模块的参数: mvn -pl project1/project1-son -am clean package 单独构建project1-son项目以及它所依赖的其它项目。 说明: mvn clean package -pl 父级模块名/子模块名 -am参数

如何保证android程序进程不到万不得已的情况下,不会被结束

最近,做一个调用系统自带相机的那么一个功能,遇到的坑,在此记录一下。 设备:红米note4 问题起因 因为自定义的相机,很难满足客户的所有需要,比如:自拍杆的支持,优化方面等等。这些方面自定义的相机都不比系统自带的好,因为有些系统都是商家定制的,难免会出现一个奇葩的问题。比如:你在这款手机上运行,无任何问题,然而你换一款手机后,问题就出现了。 比如:小米的红米系列,你启用系统自带拍照功能后

Windows11电脑上自带的画图软件修改照片大小(不裁剪尺寸的情况下)

针对一张图片,有时候上传的图片有大小限制,那么在这种情况下如何修改其大小呢,在不裁剪尺寸的情况下 步骤如下: 1.选定一张图片,右击->打开方式->画图,如下: 第二步:打开图片后,我们可以看到图片的大小为82.1kb,点击上面工具栏的“重设大小和倾斜”进行调整,如下: 第三步:修改水平和垂直的数字,此处我修改为分别都修改为50,然后保存,可以看到大小变成63.5kb,如下:

二、Maven工程的创建--JavaSEJavaEE

1、idea创建Maven JavaSE工程:  2、idea创建Maven JavaEE工程:   (1)手动创建 (2)插件方式创建 在idea里安装插件JBLJavaToWeb; 选择需要生成的项目文件后,右击: 项目的webapp文件夹出现小蓝点,代表成功。

三、Maven工程的构建

首先,创建和构建是两个概念。 构建是指将源代码、依赖库和资源文件等转换为可执行或可部署的应用程序的过程。 在这个过程中包括编译源代码、链接依赖库、打包和部署等多个步骤。 项目构建是软件开发过程中至关重要的一部分,它能够大大提高软件开发效率,使得开发人员更加专注于应用程序的开发和维护,而不必关心应用程序的构建细节。 同时,项目构建还能将多人写的代码聚合,并能够自动化项目的构建和部署,

我在高职教STM32——准备HAL库工程模板(1)

新学期开学在即,又要给学生上 STM32 嵌入式课程了。这课上了多年了,一直用的都是标准库来开发,已经驾轻就熟了。人就是这样,有了自己熟悉的舒适圈,就很难做出改变,老师上课也是如此,排斥新课和不熟悉的内容。显然,STM32 的开发,HAL 库已是主流,自己其实也在使用,只不过更换库就意味着教学内容有很大变化,自己也就迟迟没有迈出调整这一步。现在,是时候做出变化了,笔者计划保持教学项

java工程的导入jar包

由于现在学习java web,java工程导入jar包都忘记了。 在此想记录一下:工程项目名:右击 -- Build Path --add External Archives 点击会弹出一个框 ,选择你要导入的jar路径就可以了。