当前位置: 首页 > news >正文

[蓝桥杯练习]通电

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
kruskal做法(加边)

#include <bits/stdc++.h>
using namespace std;
int x[10005],y[10005],z[10005];//存储i点的x与y坐标 
int bcj[10005];//并查集 
struct Edge{//边 int v1,v2; double w;
}edge[2000005];
int cmp(Edge a, Edge b){return a.w < b.w;}
int find(int x){//并查集查找 if(bcj[x]!=x)bcj[x]=find(bcj[x]);//带路径压缩return bcj[x];
}
void merge(int v1,int v2){//并查集合并 v1=find(v1);v2=find(v2);bcj[v2]=v1;
}
int main(){//int n;cin>>n;for(int i=1;i<=n;++i)bcj[i]=i;//并查集初始化//for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>z[i];//读取结点x坐标y坐标 int cnt=0;for(int v1=1;v1<=n;++v1)for(int v2=v1+1;v2<=n;++v2){//求出任意两点的权重 double w=sqrt(pow((x[v1]-x[v2]),2)+pow((y[v1]-y[v2]),2))+pow((z[v1]-z[v2]),2);//v1的x坐标减去v2的x坐标... edge[++cnt]={v1,v2,w};}sort(edge+1,edge+cnt+1,cmp);int MSTm = 0;double sumw = 0.0;//解决了任意孤立点(一个点就是一个集合),然后对每个点作n-1个点的相连边并排序,保证每次取得是最短的,并且使用并查集避免出现环路. //取得边是离散的,总可以取完 for(int i=1;i<=cnt;++i){//依次取得边,其权重递增 if(find(edge[i].v1)!=find(edge[i].v2)){//若两边端点不属于同一个集合,则合并 merge(edge[i].v1,edge[i].v2);//每次取一条边并将其标记为一个集合,使其不出现环路 ++MSTm;sumprimzuofaw+=edge[i].w;//获取MST中最大的边 }if(MSTm==n-1)break;//n-1条边就可以构造MST }cout<<fixed<<setprecision(2)<<sumw<<endl;return 0;
}

prim做法(加点)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
vector<int> demo;
double closest[MAXN], lowcost[MAXN];
int m, n;             // m为节点的个数,n为边的数量
double G[MAXN][MAXN]; // 邻接矩阵
double prim()
{for (int i = 0; i < m; i++){lowcost[i] = INF;}for (int i = 0; i < m; i++){closest[i] = 0;}closest[0] = -1;             // 加入第一个点,-1表示该点在集合U中,否则在集合V中int num = 0,  e = 0; // e为最新加入集合的点double ans=0;while (num < m - 1)          // 加入m-1条边{int miedge = -1;double micost = INF;for (int i = 0; i < m; i++)if (closest[i] != -1){double temp = G[e][i];if (temp < lowcost[i]){lowcost[i] = temp;closest[i] = e;}if (lowcost[i] < micost)micost = lowcost[miedge = i];}ans += micost;demo.push_back(micost);closest[e = miedge] = -1;num++;}return ans;
}struct node
{double x, y, h;
} dis[MAXN];double getDistance(node a, node b)
{return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)) + pow(a.h - b.h, 2);
}int main()
{scanf("%d", &m);for (int i = 0; i < m; i++)scanf("%lf%lf%lf", &dis[i].x, &dis[i].y, &dis[i].h);for (int i = 0; i < m - 1; i++)for (int j = i + 1; j < m; j++){G[i][j] = getDistance(dis[i], dis[j]);G[j][i] = G[i][j];}printf("%.2lf", prim());// for (int i = 0; i < m - 1; i++)//     cout << demo[i] << " ";return 0;
}

相关文章:

[蓝桥杯练习]通电

kruskal做法(加边) #include <bits/stdc.h> using namespace std; int x[10005],y[10005],z[10005];//存储i点的x与y坐标 int bcj[10005];//并查集 struct Edge{//边 int v1,v2; double w; }edge[2000005]; int cmp(Edge a, Edge b){return a.w < b.w;} int find(i…...

安全算法 - 摘要算法

摘要算法是一种将任意长度的数据转换为固定长度字节串的算法。它具有以下特点和应用。 首先&#xff0c;摘要算法能够生成一个唯一且固定长度的摘要值&#xff0c;用于验证数据的完整性和一致性。无论输入数据有多长&#xff0c;生成的摘要值始终是固定长度的&#xff0c;且即…...

操作系统:动静态库

目录 1.动静态库 1.1.如何制作一个库 1.2.静态库的使用和管理 1.3.安装和使用库 1.4.动态库 1.4.1.动态库的实现 1.4.2.动态库与静态库的区别 1.4.3.共享动态库给系统的方法 2.动态链接 2.1.操作系统层面的动态链接 1.动静态库 静态库&#xff08;.a&#xff09;&…...

车载电子电器架构 —— 局部网络管理汇总

车载电子电器架构 —— 局部网络管理汇总 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明…...

网络安全 | 什么是DDoS攻击?

关注WX&#xff1a;CodingTechWork DDoS-介绍 DoS&#xff1a;Denial of Service&#xff0c;拒绝服务。DDoS是通过大规模的网络流量使得正常流量不能访问受害者目标&#xff0c;是一种压垮性的网络攻击&#xff0c;而不是一种入侵手段。NTP网络时间协议&#xff0c;设备需要…...

[Godot] 3D拾取

CollisionObject3D文档 Camera3D文档 CollisionObject3D有个信号_input_event&#xff0c;可以用于处理3D拾取。 Camera3D也有project_position用于将屏幕空间坐标投影到3D空间。 extends Node3D#是否处于选中状态 var selected : bool false #摄像机的前向量 var front : V…...

知识融合:知识图谱构建的关键技术

目录 一、引言二、知识图谱基础2.1 知识表示三元组属性图 2.2 知识抽取实体抽取关系抽取属性抽取 三、知识融合的核心问题3.1 实体识别与链接实体识别实体链接 3.2 重复实体合并方法示例 3.3 关系融合挑战方法示例 四、知识融合技术深度解析4.1 基于规则的方法规则设计原则规则…...

外贸建站:WordPress搭建外贸独立站零基础自建站完整教程(2024)

对于做外贸来说&#xff0c;拥有自己的外贸独立网站真的非常重要。在外贸领域&#xff0c;如今各平台竞争激烈&#xff0c;规则多&#xff0c;成本高&#xff0c;价格战、政策变化快&#xff0c;还存在封店风险等等因素。在这种情况下&#xff0c;拥有外贸独立站就能很好规避上…...

【教程】Kotlin语言学习笔记(五)——Lambda表达式与条件控制

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【Kotlin语言学习】系列文章 第一章 《认识Kotlin》 第二章 《数据类型》 第三章 《数据容器》 第四章 《方法》 第五章 《L…...

C++的并发世界(三)——线程对象生命周期

0.案例代码 先看下面一个例子&#xff1a; #include <iostream> #include <thread>void ThreadMain() {std::cout << "begin sub thread:" << std::this_thread::get_id()<<std::endl;for (int i 0; i < 10; i){std::cout <&…...

SAD法(附python实现)和Siamese神经网络计算图像的视差图

1 视差图 视差图&#xff1a;以左视图视差图为例&#xff0c;在像素位置p的视差值等于该像素在右图上的匹配点的列坐标减去其在左图上的列坐标 视差图和深度图&#xff1a; z f b d z \frac{fb}{d} zdfb​ 其中 d d d 是视差&#xff0c; f f f 是焦距&#xff0c; b b…...

基于DWT(离散小波变换)的图像加密水印算法,Matlab实现

博主简介&#xff1a; 专注、专一于Matlab图像处理学习、交流&#xff0c;matlab图像代码代做/项目合作可以联系&#xff08;QQ:3249726188&#xff09; 个人主页&#xff1a;Matlab_ImagePro-CSDN博客 原则&#xff1a;代码均由本人编写完成&#xff0c;非中介&#xff0c;提供…...

【威胁情报综述阅读3】Cyber Threat Intelligence Mining for Proactive Cybersecurity Defense

【威胁情报综述阅读1】Cyber Threat Intelligence Mining for Proactive Cybersecurity Defense: A Survey and New Perspectives 写在最前面一、介绍二、网络威胁情报挖掘方法和分类A. 研究方法1&#xff09; 第 1 步 - 网络场景分析&#xff1a;2&#xff09; 第 2 步 - 数据…...

在编程中使用中文到底该不该??

看到知乎上有个热门问题&#xff0c;为什么很多人反对中文在编程中的使用&#xff1f; 这个问题有几百万的浏览热度&#xff0c;其中排名第一的回答非常简洁&#xff0c;我深以为然&#xff1a; 在国内做开发&#xff0c;用中文写注释、写文档&#xff0c;是非常好的习惯&…...

PyQt6从入门到放弃

PyQt6从入门到放弃 安装PyQt6 pip install PyQt6# 查看QT和PyQT的版本 from PyQt6.QtCore import QT_VERSION_STR from PyQt6.QtCore import PYQT_VERSION_STR print(QT_VERSION_STR) print(PYQT_VERSION_STR)PyQt6模块 PyQt6类由一系列模块组成包括QtCore、QtGui、QtWidgets…...

PhpWord导入试卷

规定word导入格式 1、[单选题][2024][一般]题目1 A.选项1 B.选项2 C.选项3 D.选项4 答案&#xff1a;D 试题图片&#xff08;上传多媒体图片&#xff09;&#xff1a; 分数&#xff1a;2 答案解析&#xff1a; 2、[多选题][2024][困难]题目2 A.选项1 B.选项2 C.选项3 D.选项4 E…...

C# 运算符重载 之前的小总结

C# 中支持运算符重载&#xff0c;所谓运算符重载就是我们可以使用自定义类型来重新定义 C# 中大多数运算符的功能。运算符重载需要通过 operator 关键字后跟运算符的形式来定义的&#xff0c;我们可以将被重新定义的运算符看作是具有特殊名称的函数&#xff0c;与其他函数一样&…...

XenCenter 2024 创建一个虚拟机

前言 实现&#xff0c;创建一个虚拟机&#xff0c;内存&#xff0c;cpu&#xff0c;磁盘&#xff0c;名称&#xff0c;网卡&#xff0c;配置 Xen Center 2024 download 创建虚拟机 选择系统类型 定义虚拟机名称 选择ISO镜像库 选择主服务器 分配虚拟机内存&#xff0c;cpu资源…...

tomcat 知多少

Tomcat的缺省端口&#xff1a; 默认端口为8080&#xff0c;可以通过在tomcat安装包conf目录下&#xff0c;service.xml中的Connector元素的port属性来修改端口。 tomcat 常见 Connector 运行模式(优化)&#xff1a; 这三种模式的不同之处如下&#xff1a; BIO &#xff1a; 一…...

【详细讲解语言模型的原理、实战与评估】

&#x1f308;个人主页:程序员不想敲代码啊&#x1f308; &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家&#x1f3c6; &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...