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

2024-02-20 22:32

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

题目描述

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。经过调查评估,得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序,计算出全省畅通需要的最低成本。

输入描述:

    测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 );随后的 N 行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。

输出描述:

    对每个测试用例,在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通,则输出“?”。
示例1

输入

3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100

输出

3
?
注意:该例存在得不到最小生成树的情况,所以最后我们 对所有节点是否属于同一个集合进行判断。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#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%d",&n,&m)&&n!=0){ for( i=1;i<=n;i++){scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);}sort(edge+1,edge+1+n);for(i=1;i<=m;i++)Tree[i]=-1;int ans=0; int a,b;for( i=1;i<=n;i++){a=findroot(edge[i].a);b=findroot(edge[i].b);if(a!=b){Tree[a]=b;ans+=edge[i].cost;}} if(m==1)printf("%d\n",ans ); else{ a=findroot(1);for(i=2;i<=m;i++){b=findroot(i); if(a!=b){printf("?\n");break;}}if(i==m+1)printf("%d\n",ans );  }}return 0;
}



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



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

相关文章

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路径就可以了。