繁忙的都市(并查集、Kruskal) BFS 力扣 200.岛屿数量 深度操作系统Deepin V20正式版 2020-09-13 【OS】Bankers Algorithm 用于调用的参数太少/写入位置时发生冲突/检测到无效的异常处理程序例程 后渗透之各种维持权限的后门原理即利用 MIPS Branch Target Buffer动态分支预测(BTB) Oracle实战优化:INSERT ALL关键字的应用 Linux中MySQL数据库的使用②-----数据的基本操作 理论+实验——MySQL备份与恢复 MySQL常用数据库函数 MySQL 备份与恢复(完全备份恢复--增量备份恢复+案例演示) MySQL之基础总结部分 Oracle实战优化:递归+分析函数+OLAP函数的应用 Linux中MySQL数据库的使用③-----编码和基本数据类型 理论+实验:MySQL备份与恢复(完整备份、增量备份) “数”聚永川 “智”引未来——永川区大数据智能化产业发展强劲 从一款防疫App感受新加坡大数据智能化气息 “数”聚永川“智”引未来——永川区大数据智能化产业发展强劲 从连接量变到数据质变 物联网将二次爆发 重磅发布!猎芯半导体首创全球最小支持5G物联网的多模多频射频PA芯片 从精准授信到助企惠民,江苏银行物联网金融派上大用场 Python Selenium UI自动化_WebDriver元素_8大定位方式+总结(持续更新完善) Python中的继承、抽象基类和接口 Datawhale学习笔记【阿里云天池 金融风控-贷款违约预测】task1 赛题理解 Pytorch - torchvision计算机视觉工具库 linux 重点笔记 Ubuntu18.04安装ROS Melodic(一路到站型) 小甲鱼笔记:数据结构——线性表(一)线性表的顺序存储结构,线性表顺序存储结构的增,删,插入元素操作 实战比特币脚本编程(1) JAVA WEB DAY 01_Tomcat & Servlet Java基础算法之堆排序(Heap Sort) synchronized批量重偏向与批量撤销 终于等到了!阿里P8历时九个月整理,Java面试宝典,核心知识点笔记在此 “数字心脏”动态解析消费密码,国家级消费市场大数据联合实验室在上海先行先试 全世界运行着大约230亿台物联网设备,安全问题如何解? 物联网产业园&thinkplus解决方案中心国学讲座如期而至 都是程序员,凭什么他能站在鄙视链的顶端? 猛男必看!去小红书做程序员是种什么体验 drozer提示[Errno 2] No such file or directory 【STM32】NB-iOT BC35-G模块 AT指令应用设计指导(附代码) 【北京迅为】i.MX6ULL终结者编译LED汇编程序 Linux系统读写网卡PHY寄存器工具 洛谷:P1226 【模板】快速幂||取余运算(分治,数学) 【2020顶会KDD】AutoST:面向时空预测的高效神经网络学习模型 C/C++实现并查集disjoint_set的模板(带路径压缩优化) 实现一个百万级推送服务,除了它,还有谁 “健康守护者”——STM32标准库和HAL库的比较 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了
您的位置:首页 >开发 >

繁忙的都市(并查集、Kruskal)

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

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

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

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

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。 Input 第一行有两个整数n,m表示城市有n个交叉路口,m条道路。

接下来m行是对每条道路的描述,u,v,c表示交叉路口u和v之间有道路相连,分值为c。 Output 两个整数s,max,表示你选出了几条道路,分值最大的那条道路的分值是多少。 Sample Input 1 4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8 Sample Output 1 3 6 Hint (1≤n≤300,1≤c≤10000,1≤m≤100000)

分析:一看题目的“把所有交叉路口连通起来”、“改造道路尽量少”、“改造道路中分值最大的道路分值尽量小”,可知这符合最小生成树的定义,这道题就是最小生成树裸题。

AC代码:

#include <stdio.h>#include <algorithm>#include <string.h>struct EDGE//存边{int u;//端点1int v;//端点2int val;//边权friend bool operator<(EDGE &edge1,EDGE &edge2)//排序规则{return edge1.val<edge2.val;}}edge[100010];int n,m;//点数,边数int ans;//记录最小生成树的最大边边权int cnt=0;//记录当前已选多少条边int parent[310];//记录父节点int rank[310];//记录树层数,只有一个节点算0层inline void initialise()//初始化{for(int i=1;i<=n;++i){parent[i]=i;//开始时每个端点都是独立的,自己是自己父节点}memset(rank,0,sizeof(rank));//开始时都是0层}int find_root(int x)//寻找根节点{int x_root=x;while(parent[x_root]!=x_root){x_root=parent[x_root];}return x_root;}int union_vertices(int x,int y)//合并两个节点到一个集合{int x_root=find_root(x);int y_root=find_root(y);if(x_root==y_root){//合并将产生环,不能合并return 0;}else {//合并时进行路径压缩,层数小的树合并到层数大的树上不增加其层数//两棵层数相等的树合并,层数增1if(rank[x_root]>rank[y_root]){parent[y_root]=x_root;}else if(rank[x_root]<rank[y_root]){parent[x_root]=y_root;}else {parent[x_root]=y_root;++rank[y_root];}return 1;}}int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;++i){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val);}std::sort(edge,edge+m);//给边排序initialise();for(int i=0;i<m;++i)//从最小边开始挑选,成环则不选{if(union_vertices(edge[i].u,edge[i].v)){++cnt;ans=edge[i].val;if(cnt==n-1) break;}}printf("%d %d",n-1,ans);//打印答案return 0;}

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。