【ybtoj】繁忙都市

2024-01-30 05:18
文章标签 繁忙 都市 ybtoj

本文主要是介绍【ybtoj】繁忙都市,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

繁忙都市


题目描述

城市 C 是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接地连接起来。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:
1.改造的那些道路能够把所有的交叉路口直接或间接地连通起来。
2.在满足要求1的情况下,改造的道路尽量少。
3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。
任务:作为市规划局的你,应当作出最佳的决策,选择那些应当被修建的道路。

输入格式

第一行有两个整数n,m表示城市有n个交叉路口,m条道路。
接下来m行是对每条道路的描述u,v,c 表示交叉路口u和v之间有道路相连,分值为c。

输出格式

两个整数s,max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

输入样例

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

输出样例

3 6

解题思路

最小生成树模板题,用Kruskal按边贪心比较,最后答案为n-1和max。

Code

#include<iostream>
#include<algorithm>

这篇关于【ybtoj】繁忙都市的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

今天你City了吗?维乐Angel Revo带你穿梭都市自由随风~

当7月的热浪在都市中翻滚,你是否渴望逃离钢筋水泥的束缚,寻找一片属于自己的绿意盎然?今天你City了吗?快带上VELO Angel Revo一起抓住夏日的尾巴,用一场骑行与这座城市的风景共舞!      轻巧出行,City的轻盈      维乐Angel Revo坐垫,轻如鸿毛,却承载着都市骑行的所有需求。尺寸完美,净重轻盈,仿佛是为都市骑行量身定制的艺术品。无论是穿梭在繁忙的都市街道,还是悠闲地

【报告分享】2021中国都市青年生活态度调研-PCG(附下载)

摘要:近两年,消费者正在发生着结构性的变化,这种变化,不仅是年龄、地域、文化程度和收入这些物理性差异造成的,更是生活方式及意识形态等价值观差异带来的。都市青年作为消费主力军,是市场增长当之无愧的驱动力。所以,深入了解他们真实的生活态度显得尤为重要。所有的发现都在告诉着我们每一个世代都是无法复刻的,他们独一无二,他们看似相同却大不相同。他们用他们自己的解决之道解决一切。 来源:PCG

企业中各部门用户4点许可现状:部门之间不合理使用、繁忙的用户抢不到许可、某些无关人员抢占许可、某些用户长期占用许可

情景1. 企业中每个部门的预算是不一样的,在没有统一管理许可证时,各部门买各自的许可,或集中一起购买,然后再把费用平摊给各部门。 问题是许可放在同一个服务器里,每个用户都可以使用许可,但是A部门买了2套,B部门买了3套,C部门买了4套,实际使用时,有可能A部门使用了4个许可,B部门使用了2个许可,C部门使用了3个部门,那BC部门肯定就不满意了,这种情况该如何解决?分配功能可以解决此问题,将许可各自

解放办公室的利器!让证卡打印机轻松应对繁忙工作场景

在现代办公室中,证卡打印机已经成为不可或缺的工作利器。但是,在繁忙的工作场景中,我们经常忽视了它的保养和清洁。然而,正确的清洁和维护不仅可以延长打印机的寿命,还可以提高工作效率,确保每一次打印都是完美的。 办公室清洁新解:轻松应对工作繁忙 全方位清洁: 证卡打印机不仅外表需要清洁,内部也同样重要。我们提供全方位的清洁方案,包括外表的擦拭和内部的彻底清洁,让您的打印机焕然一新。 高效节省

繁忙的IT基础设施可能导致安全灾难

谁不喜欢新技术?特别是当它承诺让任务变得更容易并提高生产力时。渴望增加新技术,这是IT人员经常鼓励安全领导者做的事情,导致了数字化转型,使用数字技术来解决问题。智能手机,平板电脑和云计算在工作场所的数字化改造中一直处于领先地位,但物联网(IoT)的日益普及可能会彻底改变IT基础设施的外观。      然而,对于安全人员来说,数字化转型并不是一件有趣的游戏。虽然安全团队可能喜欢新技术

微信doki送信服务器繁忙,玩转Doki小程序,获得更多打榜心跳

关注Doki有惊喜之Doki小程序终于上线啦! 在Doki小程序打榜不仅可以获得额外心跳,还可以拉群好友一起打榜,更有微信打榜提醒服务。 下面就跟Doki酱一起看看,怎样玩转Doki小程序吧~ 查看完整图片 1、如何找到doki小程序 打开微信,进入发现tab后,点击“小程序”,进入小程序页面。在顶部搜索框,搜索“腾讯视频doki”,就可以找到doki小程序。 查看完整图片查看完整图片查看完整图

无比繁忙

第一次体会到什么是充实……也许以前也有体会到过?忘了忘了。 是因为我花了一个下午的时间弄懂了cache的工作机制,还有乱七八糟的算法……《软件设计师应试教程》,第四讲。 接下来还会有两个月的这样的下午。充实的生活真美好啊。 我也终于绕了个圈圈回来了,吃饭,还是得靠这玩意。为了不让120块的报名费和120块的资料钱打了水漂,我还真不得不努点力了。

城市白模:裸眼3D下的未来都市构想

随着科技的飞速发展,城市规划与建设已经迈入了一个全新的时代。在这个时代里,“城市白模”成为了设计师、建筑师、城市规划者乃至普通市民的热门话题。那么,什么是“城市白模”?它又如何改变我们对城市的认知与期待呢? 城市白模,顾名思义,是城市的“白色模型”。它是一个没有贴图、没有细节渲染的三维模型,但正是这样的“裸眼3D预览”,让人们能够更直观地感受到城市的未来面貌。它不仅仅是一个视觉上的呈现,更是

通过VMware创建虚拟机,虚拟机开机经常一直黑屏 关闭点击虚拟机提示:虚拟机***繁忙

通过VMware创建虚拟机,虚拟机开机经常一直黑屏: 如图: 而且,关闭点击虚拟机提示:虚拟机***繁忙,如下界面: 解决方案 解决方案1. 原因: 为什么要netsh winsock reset 网上有一种说法,是因为启动了wegame之后,wegame修改了一些网络的相关参数,导致和vm的配置冲突。下面是知乎网友的解释:虚拟机和主机之间的通信,基本上是以 socket 的方式进行通信

P2330 [SCOI2005] 繁忙的都市

Problem: P2330 [SCOI2005] 繁忙的都市 文章目录 思路解题方法复杂度Code 思路 这是一道最小生成树(Minimum Spanning Tree)的问题。我们可以使用Kruskal算法来解决。 解题方法 首先,我们需要将所有的道路按照分值从小到大进行排序。然后,我们从分值最小的道路开始,依次判断这条道路的两个交叉路口是否已经连通。如果