洛谷 P2330 05四川 繁忙的都市

2023-10-09 05:32

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

题目描述

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

输入输出格式
输入格式:

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

输出格式:

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

输入输出样例

输入样例#1:
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

输出样例#1:
3 6


给一张图,求最大生成树。
用Kruskal算法即可


#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ans,f[301];
struct tree
{int x,y,val;
}a[50000];
bool comp(const tree &c,const tree &d)
{return c.val<d.val;
}
int fnd(int x)
{if(f[x]==x)return x;return f[x]=fnd(f[x]);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);sort(a+1,a+m+1,comp);for(int i=1;i<=m;i++)if(fnd(a[i].x)!=fnd(a[i].y)){f[fnd(a[i].y)]=fnd(a[i].x);ans=max(ans,a[i].val);}printf("%d %d\n",n-1,ans);return 0;
}

这篇关于洛谷 P2330 05四川 繁忙的都市的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

忽略某些文件 —— Git 学习笔记 05

忽略某些文件 忽略某些文件 通过.gitignore文件其他规则源如何选择规则源参考资料 对于某些文件,我们不希望把它们纳入 Git 的管理,也不希望它们总出现在未跟踪文件列表。通常它们都是些自动生成的文件,比如日志文件、编译过程中创建的临时文件等。 通过.gitignore文件 假设我们要忽略 lib.a 文件,那我们可以在 lib.a 所在目录下创建一个名为 .gi

C++入门(05-2)从命令行执行C++编译器_GCC

文章目录 GCC编译器1. 下载MinGW-w64,安装(不推荐)2. 使用MSYS2安装MinGW-w64(推荐)2.1 安装MSYS22.2 初始化和更新2.3 安装MinGW-w64编译器2.3 在MSYS2 Shell中导航到代码目录2.4 使用 g++ 编译2.5 运行可执行文件 GCC编译器 GCC(GNU Compiler Collection)是一个开源编译器集

C++入门(05)从命令行执行C++编译器_MSVC

文章目录 1.C++ 编译器2. 常用 C++ 编译器MSVC(Microsoft Visual C++)GCC(GNU Compiler Collection)Clang 3. MSVC 编译器3.1 开发者命令提示符3.2 编译 C++ 代码 1.C++ 编译器 将C++源代码(扩展名为 .cpp )转换成计算机可以运行的可执行程序 编译器会检查代码的语法和语义,生成相应

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

龙芯+FreeRTOS+LVGL实战笔记(新)——05部署主按钮

本专栏是笔者另一个专栏《龙芯+RT-Thread+LVGL实战笔记》的姊妹篇,主要的区别在于实时操作系统的不同,章节的安排和任务的推进保持一致,并对源码做了改进和优化,各位可以先到本人主页下去浏览另一专栏的博客列表(目前已撰写36篇,图1所示),再决定是否订阅。此外,也可以前往本人在B站的视频合集(图2所示)观看所有演示视频,合集首个视频链接为: 借助RT-Thread和LVGL

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

【SpringMVC学习05】SpringMVC中的异常处理器

SpringMVC在处理请求过程中出现异常信息交由异常处理器进行处理,自定义异常处理器可以实现一个系统的异常处理逻辑。 异常处理思路 我们知道,系统中异常包括两类:预期异常和运行时异常(RuntimeException),前者通过捕获异常从而获取异常信息,后者主要通过规范代码开发、测试通过手段减少运行时异常的发生。系统的dao、service、controller出现异常都通过throws E

学习硬件测试05:NTC(ADC)+正弦波(DAC)+DMA(ADC+DAC)(P73、P76、P78)

文章以下内容全部为硬件相关知识,鲜有软件知识,并且记的是自己需要的部分,大家可能看不明白。 一、NTC(ADC) 1.1实验现象 本实验用 NTC 采集温度,数码管实时显示温度数据(整数),左下角 USB 小串口每隔 1S 打印温度信息。 1.2硬件电路 NTC 电阻是一个模拟温度传感器,随着温度的升高,电阻值逐渐减小。电路简单介绍如下: 电源滤波电容在 25℃ 室温下 NTC 电

python+selenium2学习笔记unittest-05测试用例实例

看一下非常简单的目录结构 test_baidu from selenium import webdriverimport unittestimport timeclass MyTest(unittest.TestCase):def setUp(self):self.driver = webdriver.Firefox()self.driver.maximize_window()self