并查集与最小生成树
并查集
HDOJ-1232 畅通工程
题目: 省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通,输入现有城镇道路统计表(表中列出了每条道路直接连通的城镇),求最少还需要建设的道路数量。(城镇从1到N编号)
思路:
将每组互相连通的城市视为一个不相交集合,不与其他城市连通的城市也视为一个集合。
“使任何两个城镇间都可以实现交通”即将所有集合合并为一个集合。
题目每行输入,定义该行的两个元素属于同一个集合,将这两个元素所属集合合并。
本组输入处理完成之后,满足set[i]==i的城镇均为集长(预处理: set[i]=i,i=1,2,…,n),统计这样的城镇个数,减去1,即为最少需要建设的道路数量。
#include<cstdio>
int set[1005];
//set[i]=①i,则i表示本集合,并是集合对应树的根;②j,j!=i,则j是i的父节点
int find(int x)//x为待查找城镇的编号{while(set[x]!=x) x=set[x];return x;}//输出集长
int h[1005];//h[i]代表以i为集长的集树的深度
void merge(int m1,int m2){//合并两个城镇所在的集合m1=find(m1);m2=find(m2);if(m1!=m2){//查找出两个城镇的集长,不同则合并if(h[m1]==h[m2]) {h[m1]++;set[m2]=m1;}//如果深度相同,集合m2转接至集合m1,集合m1深度+1else if(h[m1]<h[m2]) set[m1]=m2;//深度小的树合并到深度大的树else set[m2]=m1;}
}
int main(){int n;while(scanf("%d",&n)&&n){//n代表城镇数量int i,m,m1,m2;scanf("%d",&m);//m代表已有道路数量for(i=1;i<=n;i++) set[i]=i;//各个城市初始化为一个独立的集合,城市编号从1开始 for(i=1;i<=n;i++) h[i]=1;//各集树深度(层数)初始化为1while(m--){//依次读入各条道路scanf("%d%d",&m1,&m2);//m1,m2代表当前道路连通的两个城镇merge(m1,m2);}int count=0;//count代表独立集合个数for(i=1;i<=n;i++)if(set[i]==i) count++;count--;//最少建设道路数=独立集合个数-1printf("%d\n",count);}return 0;
}
HDOJ-1856 More is better
题目: 在一个房间里有10000000个男孩,他们的编号依次为1,2,…, 10000000。在各个互相认识(直接或间接)的男孩之间组成了许多的朋友圈,输入关系表,表中每行中的两个男孩直接认识,输出房间内最大的朋友圈的尺寸(包含人数)。
思路:
每组互相认识的男孩属于同一个朋友圈,将不与其他男孩认识的男孩也视为一个朋友圈。
题目的任务是确定朋友圈的最大尺寸。
题目每行输入,定义该行的两个编号对应的男孩相互认识,属于同一个朋友圈,将这两个男孩所属朋友圈合并。
开辟数组记录朋友圈尺寸,两个朋友圈合并时,将它们的尺寸相加。
本组输入处理完成之后,找出朋友圈的最大尺寸。
由于数据量较大,要进行路径压缩。
#include<cstdio>
int set[10000005];
//set[i]=①i,则i表示本集合,并是集合对应树的根;②j,j!=i,则j是i的父节点
int find(int i){//i为待查找男孩的编号int r=i;while(set[r]!=r) r=set[r];int t;while(i!=r){//修改查找路径中所有节点t=set[i];set[i]=r;//使i指向ri=t;}return r;//输出圈长
}
int h[10000005];//h[i]代表以i为圈长的集树的深度
int size[10000005];//size[i]代表以i为圈长的朋友圈的尺寸
void merge(int m1,int m2){//合并两个男孩所在的朋友圈m1=find(m1);m2=find(m2);if(m1!=m2){//查找出两个朋友圈的圈长,不同则合并if(h[m1]==h[m2]) {h[m1]++;set[m2]=m1;size[m1]+=size[m2];}//朋友圈尺寸对应合并else if(h[m1]<h[m2]) {set[m1]=m2;size[m2]+=size[m1];}else {set[m2]=m1;size[m1]+=size[m2];}}
}
int main(){int n;while(scanf("%d",&n)!=EOF){//n代表朋友对数量int i,m1,m2;for(i=1;i<=n;i++) set[i]=i;//各个男孩初始化为一个独立的朋友圈,朋友圈编号从1开始 for(i=1;i<=n;i++) {h[i]=1;size[i]=1;}//各朋友圈尺寸初始化为1for(i=1;i<=n;i++){scanf("%d%d",&m1,&m2);//m1,m2代表当前认识的两个男孩merge(m1,m2);}int max=1;//max代表朋友圈最大尺寸for(i=1;i<=n;i++)if(size[i]>max) max=size[i];printf("%d\n",max);}return 0;
}
最小生成树
给定无向图G=(V,E),连接G中所有点,且是E的子集的树称为G的生成树。所有路权值总和最小的生成树称为最小生成树。
求最小生成树的Kruskal算法步骤:
一、把原始图的N个节点看成N个独立集合;
二、所有边从短到长排序,每次选取当前最短的边,如果两端是否属于不同的集合,进行合并;
三、循环操作步骤二,直到有N-1条边;
将每个村庄看作一个结点,题目可归结为求连接所有结点的最小生成路的权值之和。
HDOJ-1233 还是畅通工程
题目: 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现交通,输入现有村庄分布统计表(表中列出了任意两个村庄之间的距离),计算需要建设的最小的公路总长度。(乡村从1到N编号)
#include<cstdio>
#include<algorithm>
using namespace std;
struct road{int c1,c2;//c1,c2代表两个村庄编号int d;//d代表它们之间的距离}r[5000];
bool cmp(road x,road y){return x.d<y.d;}//距离从小到大排序
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(m2);if(m1!=m2){//查找出两个村庄的集长,不同则合并if(h[m1]==h[m2]) {h[m1]++;set[m2]=m1;}else if(h[m1]<h[m2]) set[m1]=m2;else set[m2]=m1;return 1;}return 0;
}
int main(){int n,i;while(scanf("%d",&n)&&n){//n代表村庄数量int nm=n*(n-1)/2;for(i=0;i<nm;i++)//依次读入各村庄间距离scanf("%d%d%d",&r[i].c1,&r[i].c2,&r[i].d);sort(r,r+nm,cmp); for(i=1;i<=n;i++) set[i]=i; for(i=1;i<=n;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量int sd=0;//sd代表已经建造的道路里程for(i=0;i<nm;i++){if(merge(r[i].c1,r[i].c2)==1)//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//两村庄间距离计入道路里程if(sn==n-1) break;}printf("%d\n",sd);}return 0;
}
HDOJ-1879 继续畅通工程
题目: 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现交通,输入现有村庄道路统计表(表中列出了任意两个乡村间修建道路的费用,以及该道路是否已经修通的状态),计算全省畅通需要的最低成本。(乡村从1到N编号)
【思路】本题坑点:有些村庄已经连通,建造这些已经连通的道路所需成本(即权值)应该记为0。
#include<cstdio>
#include<algorithm>
using namespace std;
struct road{int c1,c2;//c1,c2代表两个村庄编号int d;//d代表此两村庄间道路的成本}r[5000];
bool cmp(road x,road y){return x.d<y.d;}//距离从小到大排序
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(m2);if(m1!=m2){//查找出两个村庄的集长,不同则合并if(h[m1]==h[m2]) {h[m1]++;set[m2]=m1;}else if(h[m1]<h[m2]) set[m1]=m2;else set[m2]=m1;return 1;}return 0;
}
int main(){int n,i;while(scanf("%d",&n)&&n){//n代表村庄数量int nm=n*(n-1)/2;int s;//s代表当前道路修建状态for(i=0;i<nm;i++)//依次读入各村庄间道路{scanf("%d%d%d%d",&r[i].c1,&r[i].c2,&r[i].d,&s);if(s==1) r[i].d=0;}//如果道路已修建,未来成本为0sort(r,r+nm,cmp); for(i=1;i<=n;i++) set[i]=i;for(i=1;i<=n;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量int sd=0;//sd代表累计花费的成本for(i=0;i<nm;i++){if(merge(r[i].c1,r[i].c2)==1)//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//计入成本if(sn==n-1) break;}printf("%d\n",sd);}return 0;
}
HDOJ-1875 畅通工程再续
题目: 有一个叫“百岛湖”的地方,其中的居民生活在不同的小岛上。该景区“畅通工程”的目标是通过在符合条件的岛间建桥(如果2个小岛之间的距离d满足10<=d<=1000,则符合条件)使全湖任何两个小岛间都可以实现陆上交通。输入各小岛的位置坐标,桥的价格为 100元/米,计算全湖畅通需要的最低成本。
思路:
最小生成树。
相比1007变化之处:需要自行计算各小岛间距离;建桥对距离有要求。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct dao{int num;//num代表小岛编号int x,y;//x,y代表小岛坐标}xd[105];
struct road{int num1,num2;//num1,num2代表两个小岛编号double d;//d代表两个小岛间距离}r[5000];
bool cmp(road x,road y){return x.d<y.d;}
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(m2);if(m1!=m2){if(h[m1]==h[m2]) {h[m1]++;set[m2]=m1;}else if(h[m1]<h[m2]) set[m1]=m2;else set[m2]=m1;return 1;}return 0;
}
int main(){int t,c,i,j;scanf("%d",&t);while(t--){scanf("%d",&c);//c代表小岛数量for(i=1;i<=c;i++)//依次发放小岛编号,读入坐标{xd[i].num=i;scanf("%d%d",&xd[i].x,&xd[i].y);}double dis;//dis代表当前两个小岛间距离int cm=0;//cm代表长度符合条件的道路数量for(i=1;i<=c;i++)for(j=i+1;j<=c;j++){//依次计算小岛间距离dis=sqrt((xd[i].x-xd[j].x)*(xd[i].x-xd[j].x)+(xd[i].y-xd[j].y)*(xd[i].y-xd[j].y));if(dis>=10&&dis<=1000) {cm++;r[cm].num1=i;r[cm].num2=j;r[cm].d=dis;}}if(cm>=c-1){sort(r+1,r+1+cm,cmp); for(i=1;i<=c;i++) set[i]=i;for(i=1;i<=c;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量double sd=0;//sd代表累计建造的道路里程for(i=1;i<=cm;i++){if(merge(r[i].num1,r[i].num2)==1)//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//计入里程if(sn==c-1) break;}printf("%.1lf\n",100.0*sd);}else printf("oh!\n");}return 0;
}
POJ-2031 Building a Space Station
题目:
空间站由多个半径不同的球形单元组成。反常的是,两个单元可以彼此接触,甚至可以有交叉重叠。
输入各单元的三维坐标和半径。试将所有单元用走廊连接起来(走廊的端点在单元的表面上),并使走廊总长度最短。(两个接触或交叉重叠的单元视为已连接)
思路:
最小生成树
接触或交叉重叠判定:球心距<=半径之和
两个单元直接相连的最短路径并不是球心距,而是球心距-两者半径之和。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct dao{int num;//num代表单元编号double x,y,z,r;//x,y,z代表单元坐标,r为单元半径 }xd[105];
struct road{int num1,num2;//num1,num2代表两个单元编号double d;//d代表两个单元间距离}r[5000];
bool cmp(road x,road y){return x.d<y.d;}
int set[105];
int find(int x){while(set[x]!=x) x=set[x];return x;}
int h[105];
int merge(int m1,int m2){m1=find(m1),m2=find(m2);if(m1!=m2){if(h[m1]==h[m2]) {h[m1]++;set[m2]=m1;}else if(h[m1]<h[m2]) set[m1]=m2;else set[m2]=m1;return 1;}return 0;
}
int main(){int c,i,j;while(scanf("%d",&c)&&c){//c代表单元数量for(i=1;i<=c;i++)//依次发放单元编号,读入坐标{xd[i].num=i;scanf("%lf%lf%lf%lf",&xd[i].x,&xd[i].y,&xd[i].z,&xd[i].r);}double dis,dism;//dis代表当前两个单元球心间距离,dism为最短距离 int cm=0;//cm为尚未建设的道路数量 for(i=1;i<=c;i++) set[i]=i;for(i=1;i<=c;i++) h[i]=1;int sn=0;//sn代表已经建造的道路数量for(i=1;i<=c;i++)for(j=i+1;j<=c;j++){//依次计算单元间距离dis=sqrt(pow(xd[i].x-xd[j].x,2)+pow(xd[i].y-xd[j].y,2)+pow(xd[i].z-xd[j].z,2));dism=dis-xd[i].r-xd[j].r;if(dism>0&&fabs(dism)>1e-6) {cm++;r[cm].num1=i;r[cm].num2=j;r[cm].d=dism;}else if(merge(i,j)) sn++;//关键}double sd=0;//sd代表累计建造的道路里程if(sn<c-1){sort(r+1,r+1+cm,cmp); for(i=1;i<=cm;i++){if(merge(r[i].num1,r[i].num2))//进行了合并{sn+=1;//新建一条道路sd+=r[i].d;}//计入里程if(sn==c-1) break;}}printf("%.3lf\n",sd);}return 0;
}
【总结】两个相连的单元,如果已经处于同一个集合,则图的边数不应增加。
相关文章:
并查集与最小生成树
并查集 HDOJ-1232 畅通工程 题目: 省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通,输入现有城镇道路统计表(表中列出了每条道路直接连通的城镇),求最少还需要建设的道路数量。(城镇从1到…...
平面运动机器人的传感器外参标定
简述 对任意两个传感器进行外参标定可以采用手眼标定算法来完成,但是,传统手眼标定算法对于运动具有一定的要求,可以证明,至少需要两个以上轴角方向不同的旋转运动才可以正确估计出外参旋转,因此,如果使用…...

【星海随笔】SDN neutron (二) Neutron-plugin(ML2)
Neutron架构之Neutron-plugin Core-plugin(ML2)篇 Neutron-server接收两种请求: REST API请求:接收REST API请求,并将REST API分发到对应的Plugin(L3RouterPlugin)。 RPC请求:接收Plugin agent请求&#…...

野火i.MX6ULL开发板检测按键evtest(Linux应用开发)
之前一直查找不到evtest,因为没有下载成功,很可能是网络不好,下次可以软件源可以换成国内大学镜像网站。 重新断开板子电源启动,再次连接网络,下载evtest成功!!...

k8s存储
nfs 理论上nfs 其实并不是存储设备,它是一种远程共享存储服务。 k8s 存储卷 volume emptyDir:可以实现pod中的容器之间共享数据, 但是存储卷不能持久化数据,且会随着pod的生命周期一起删除。 hostpash:可以实现持久…...

数据分析实战 | 贝叶斯分类算法——病例自动诊断分析
目录 一、数据及分析对象 二、目的及分析任务 三、方法及工具 四、数据读入 五、数据理解 六、数据准备 七、模型训练 八、模型评价 九、模型调参 十、模型预测 一、数据及分析对象 CSV文件——“bc_data.csv” 数据集链接:https://download.csdn.net/d…...

实用技巧:嵌入式人员使用http服务模拟工具模拟http服务器测试客户端get和post请求
文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/134305752 红胖子(红模仿)的博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软硬结…...
P9836 种树
容易想到分解因数。 对于一个数 p p p 的因数个数,假设它可以被分解质因数成 a 1 i 1 a 2 i 2 a 3 i 3 ⋯ a k c k a_1^{i_1} a_2^{i_2} a_3^{i_3}\cdots a_k^{c_k} a1i1a2i2a3i3⋯akck 的形式,则其因数个数为 ( i 1 1 ) ( i 2 1 )…...

C# 查询腾讯云直播流是否存在的API实现
应用场景 在云考试中,为防止作弊行为的发生,会在考生端部署音视频监控系统,当然还有考官方监控墙系统。在实际应用中,考生一方至少包括两路直播流: (1)前置摄像头:答题的设备要求使…...

JAVA开源项目 于道前端项目 启动步骤参考
1. 安装 启动过程有9个步骤: 1.1 安装 Node JS , V18版本的 (安装步骤省略) 1.2 安装 npm install -g yarn ,node JS里边好像自带npm ,通过npm的命令安装 yarn 1.3 切换到项目中去安装,npm install &a…...

深入理解ElasticSearch分片
1. 路由计算 当索引一个文档的时候,文档会被存储到一个主分片中。 Elasticsearch 如何知道一个文档应该存放到哪个分片中呢?当我们创建文档时,它如何决定这个文档应当被存储在分片 1 还是分片 2 中呢?首先这肯定不会是随机的&…...

【Python】AppUI自动化—appium自动化元素定位、元素事件操作(17)下
文章目录 前言一.Appium 元素定位1.定位方式种类2.如何定位2.1 id定位2.2 className定位2.3 content-desc 定位2.4 Android Uiautomator定位4.1 text定位4.2 text模糊定位4.3 text正则匹配定位4.4 resourceId定位4.5 resourceId正则匹配定位4.6 className定位4.7 className正则…...
SpringBoot使用MyBatis多数据源
SpringBoot使用MyBatis多数据源 我们以 Mybatis Xml和注解两种版本为例,给大家展示如何如何配置多数据源。 1、注解方式 数据库文件: DROP TABLE IF EXISTS users; CREATE TABLE users (id bigint(20) NOT NULL AUTO_INCREMENT COMMENT 主键id,userN…...

小程序版本审核未通过,需在开发者后台「版本管理—提交审核——小程序订单中心path」设置订单中心页path,请设置后再提交代码审核
小程序版本审核未通过,需在开发者后台「版本管理—提交审核——小程序订单中心path」设置订单中心页path,请设置后再提交代码审核 因小程序尚未发布,订单中心不能正常打开查看,请先发布小程序后再提交订单中心PATH申请 初次提交…...

Netty入门指南之NIO Selector监管
作者简介:☕️大家好,我是Aomsir,一个爱折腾的开发者! 个人主页:Aomsir_Spring5应用专栏,Netty应用专栏,RPC应用专栏-CSDN博客 当前专栏:Netty应用专栏_Aomsir的博客-CSDN博客 文章目录 参考文献前言问题解…...

Spring Cloud学习(六)【统一网关 Gateway】
文章目录 网关的功能搭建网关服务路由断言工厂Route Predicate Factory路由过滤器 GatewayFilter过滤器执行顺序跨域问题处理 网关的功能 网关功能: 身份认证和权限校验服务路由、负载均衡请求限流 在SpringCloud中网关的实现包括两种: gatewayzuul …...

基于单片机的空调智能控制器的设计
**单片机设计介绍,基于单片机的空调智能控制器的设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的空调智能控制器需要具备输入输出端口、定时器、计数器等模块,以便对空调进行精确控制。下…...

Spring Boot自动配置原理、实战、手撕自动装配源码
Spring Boot自动配置原理 相比较于传统的 Spring 应用,搭建一个 SpringBoot 应用,我们只需要引入一个注解 SpringBootApplication,就可以成功运行。 前面四个不用说,是定义一个注解所必须的,关键就在于后面三个注解&a…...

111111111111111
全局锁 就是对整个数据库进行加锁,加锁之后整个数据库就处于只读状态,后续的DML写语句,DDL语句,以及对更新事务的提交操作都会被阻塞,典型地使用场景就是做整个数据库的逻辑备份,对所有的表进行锁定&#x…...

React动态生成二维码和毫米(mm)单位转像素(px)单位
一、使用qrcode.react生成二维码,qrcode.react - npm 很简单,安装依赖包,然后引用就行了 npm install qrcode.react或者 yarn add qrcode.react直接上写好的代码 import React, {useEffect, useState} from react; import QRCode from qr…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!
今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等,设置经线、纬线都以10间隔显示。 2、需要插入背会归线…...

Redis上篇--知识点总结
Redis上篇–解析 本文大部分知识整理自网上,在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库,Redis 的键值对中的 key 就是字符串对象,而 val…...