【代码随想录day57】【C++复健】 53. 寻宝(prim算法);53. 寻宝(kruskal算法)
53. 寻宝(prim算法)
好像在研究生的算法课上学过prim算法和kruskal算法,不过当时只是了解了一下大致的概念和流程,并没有涉及到如何去写代码的部分,今天也算是学习了一下这两个算法的代码应该如何去实现,还是挺长见识的。
整体做的时候,是一个边看解析边自己做的过程,因为我自己哪怕是看完了卡哥的思路解析仍然有很多不是很确定的地方,这些地方也相当容易出错,一一列举一下遇到的各种疑问:
1 我在定义这个图的时候应该用邻接矩阵还是邻接表?
问了下GPT说是都可以,那当然还是用邻接数组会更好实现一点。并且本题当中边还是很密集的。
2 mindist和inTree如何定义?
一维即可,长度为v+1,因为0号位我们会进行弃用。
3 是否需要专门的处理初始化逻辑的代码?
从卡哥写的代码里还是能看出来是不需要的,只要我们一开始给dis定义成最大值或者比10001更大的值,就会自动把第一个节点放进去,并且顺便更新一下mindist。
解决这三个问题之后,整个prim算法的逻辑因为已经看过解析的思路了,反而自己也能写出来了。
#include<iostream>
#include<vector>
using namespace std;int main(){int v,e;cin >> v >> e;vector<vector<int>> grid(v+1, vector<int>(v+1, 10001));for(int i=0; i<e; i++){int left, right, weight;cin >> left >> right >> weight;grid[left][right] = weight;grid[right][left] = weight;}vector<int> mindist(v+1, 10001);vector<bool> inTree(v+1);int result = 0;for(int i=0; i<v; i++){int dis = 10002;int pos = -1;for(int j=1; j<=v; j++){if(!inTree[j] && mindist[j] < dis){dis = mindist[j];pos = j;}}if(i != 0){result += dis;}inTree[pos] = true;for(int k=1; k<=v; k++){if(!isInTree[j] && grid[pos][k] < mindist[k]){mindist[k] = grid[pos][k];}}}cout << result;return 0;
}
53. 寻宝(kruskal算法)
同样是看了思路之后尝试自己实现,不过自己想去实现当然也是有不小的难度的。
1 看了解释知道要保存变并且按照权值排序,但应该怎么做?
想了一下好像邻接矩阵和邻接表都不太好的样子,但是自己又不知道用什么,最后一看解析,好嘛,结构体,这个是真的想不到,毕竟从学图论开始就没用过这个东西。包括后面这个vector<edge>,也是没想到还可以这么用。
2 sort函数,哪个库的,怎么用?
因为忘写#include <algorithm>而没过。不过比起这个倒不如说,根本就没有写的意识,不知道sort函数还得调个库。然后就是老生常谈的传cmp问题,如果是在类内的话需要写的很复杂:
static bool cmp(const Edge& a, const Edge& b) {return a.val < b.val;}
原因都忘记了,问问GPT复习一下:
- 普通成员函数 默认包含一个隐式的
this指针参数,指向调用它的对象。 - 例如,
cmp在类内是一个普通成员函数时,其实际签名类似于:
这使得它只能通过具体的类对象调用,或者通过对象的指针调用。bool cmp(const Edge& a, const Edge& b, Solution* this); - 但是
std::sort接受的是一个普通函数指针,不支持这种额外的this参数,因此直接传递普通成员函数会出错。
但是这次是在类外。所以简单这么写也不会报错:
bool cmp(Edge a, Edge b){return a.val < b.val;
}
或者像卡哥的写法一样用lambda表达式:
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});
3 试图去写一个intree变量统计点在不在里面,但并查集就是干这个用的。所以理解的还不是很到位。
#include<iostream>
#include<vector>
#include <algorithm> // for sort
using namespace std;vector<int> father;struct Edge {int l, r, val;
};void init(){for(int i=0; i<father.size(); i++){father[i] = i;}
}int find(int u){return u==father[u] ? u: father[u] = find(father[u]);
}bool issame(int u, int v){u = find(u);v = find(v);return u == v;
}
bool join(int u, int v){u = find(u);v = find(v);if(u==v){return false;}father[v] = u;return true;
}bool cmp(Edge a, Edge b){return a.val < b.val;
}int main(){int v,e;cin >> v >> e;father = vector<int> (v+1);init();int sum = 0;vector<Edge> edges;for(int i=0; i<e; i++){int left, right, weight;cin >> left >> right >> weight;edges.push_back({left, right, weight});}sort(edges.begin(), edges.end(), cmp);for(int i=0; i<e; i++){bool result = join(edges[i].l, edges[i].r);if(result){sum += edges[i].val;}}cout << sum;return 0;
}
相关文章:
【代码随想录day57】【C++复健】 53. 寻宝(prim算法);53. 寻宝(kruskal算法)
53. 寻宝(prim算法) 好像在研究生的算法课上学过prim算法和kruskal算法,不过当时只是了解了一下大致的概念和流程,并没有涉及到如何去写代码的部分,今天也算是学习了一下这两个算法的代码应该如何去实现,还…...
C++中多态
1) 什么是多态性?C中如何实现多态? 多态性是指通过基类指针或引用调用派生类的函数,实现不同的行为 多态性可以提高代码的灵活性和可扩展性,使程序能够根据不同的对象类型执行不同的操作。 2)C中如何实现多态&#…...
【实现多网卡电脑的网络连接共享】
电脑A配备有两张网卡,分别命名为eth0和eth1(对于拥有超过两张网卡的情况,解决方案相似)。其中,eth0网卡能够连接到Internet,而eth1网卡则通过网线直接与另一台电脑B相连(在实际应用中࿰…...
算力介绍与解析
算力(Computing Power)是指计算机系统在单位时间内处理数据和执行计算任务的能力。算力是衡量计算机性能的重要指标,直接影响计算任务的速度和效率。 算力的分类和单位 a. 基础算力:以CPU的计算能力为主。适用于各个领域的计算。…...
解决 MyBatis 中空字符串与数字比较引发的条件判断错误
问题复现 假设你在 MyBatis 的 XML 配置中使用了如下代码: <if test"isCollect ! null"><choose><when test"isCollect 1">AND exists(select 1 from file_table imgfile2 where task.IMAGE_SEQimgfile2.IMAGE_SEQ and im…...
python 词向量的代码解读 self.word_embeds = nn.Embedding(vocab_size, embedding_dim) 解释下
在PyTorch中,nn.Embedding 是一个用于将稀疏的离散数据表示为密集的嵌入向量的模块。这在自然语言处理(NLP)任务中非常常见,例如在处理单词或字符时,我们通常需要将这些离散的标识符转换为可以被神经网络处理的连续值向…...
记一次:使用C#创建一个串口工具
前言:公司的上位机打不开串口,发送的时候设备总是关机,因为和这个同事关系比较好,编写这款软件是用C#编写的,于是乎帮着解决了一下(是真解决了),然后整理了一下自己的笔记 一、开发…...
Android Studio新版本的一个资源id无法找到的bug解决
Android Studio新版本的一个资源id无法找到的bug解决 文章目录 Android Studio新版本的一个资源id无法找到的bug解决一、前言二、Android Studio的无法获取到资源id的bug1、一段简单的Java代码1、错误现象2、错误解决方法 三、其他1、小结2、gradle.properties文件 其他相关属性…...
Datawhale AI冬令营(第一期)--零基础定制你的专属大模型
本文主要简述如何快速完成和一些小细节 第一步下载嬛嬛数据集 数据来源:self-llm/dataset/huanhuan.json at master datawhalechina/self-llm GitHub 注意:1.一定是数据集下载完成一定是.json结尾的 2.这个是github的网址,可能会遇到打不开的情况 …...
LLMs之APE:基于Claude的Prompt Improver的简介、使用方法、案例应用之详细攻略
LLMs之APE:基于Claude的Prompt Improver的简介、使用方法、案例应用之详细攻略 目录 Prompt Improver的简介 0、背景痛点 1、优势 2、实现思路 Prompt优化 示例管理 提示词评估 Prompt Improver的使用方法 1、使用方法 Prompt Improver的案例应用 1、Kap…...
【Unity人形布娃娃插件】Ragdoll Animator
Ragdoll Animator 是一款为 Unity 引擎开发的插件,专注于让角色在运行时动态地切换到布娃娃物理系统(Ragdoll Physics)。该插件帮助开发者轻松创建逼真的角色动画过渡效果,尤其适用于需要角色碰撞、摔倒、受击或其他物理反应的场景…...
跨团队协作中目标一致性至关重要
在团队协作的复杂拼图里,目标一致性是那根贯穿始终的主线,缺之则拼图难成,团队亦难达预期之效。 且看这样一个实例:部门承接了业务方一项紧急的数据处理需求,此任务犹如一座亟待攀登的险峰,落在了 A 团队…...
Excel的文件导入遇到大文件时
Excel的文件导入向导如何把已导入数据排除 入起始行,选择从哪一行开始导入。 比如,前两行已经导入了,第二次导入的时候排除前两行,从第三行开始,就将导入起始行设置为3即可,且不勾选含标题行。 但遇到大文…...
使用字典进行动态编程
在你的程序中,你想要执行各种计算,例如计算卫星的总数。 此外,当你进行更高级的编程时,你可能会发现你需要从文件或数据库中加载此类信息,而不是直接编码到 Python 中。 为了帮助支持这些场景,Python 使你…...
机器学习02-发展历史补充
机器学习02-发展历史补充 文章目录 机器学习02-发展历史补充1-机器学习个人理解1-初始阶段:统计学习和模式识别(20世纪50年代至80年代)2-第二阶段【集成时代】【核方法】(20世纪90年代至2000年代初期)3-第三阶段【特征…...
全国青少年信息学奥林匹克竞赛(信奥赛)备考实战之计数器与累加器(一)
学习背景: 在现实生活中一些需要计数的场景下我们会用到计数器,如空姐手里记录乘客的计数器,跳绳手柄上的计数器等。累加器是累加器求和,以得到最后的结果。计数器和累加器它们虽然是基础知识,但是应用广泛࿰…...
Android的SurfaceView和TextureView介绍
文章目录 前言一、什么是SurfaceView ?1.1 SurfaceView 使用示例1.2 SurfaceView 源码概述1.3 SurfaceView 的构造与初始化1.4 SurfaceHolder.Callback 回调接口1.5 SurfaceView 渲染机制 二、什么是TextureView?2.1 TextureView 使用示例2.2 TextureVie…...
Scala的集合
1 集合简介 1)Scala 的集合有三大类:序列 Seq、集 Set、映射 Map,所有的集合都扩展自 Iterable 特质。 2)对于几乎所有的集合类,Scala 都同时提供了可变和不可变的版本,分别位于以下两 个包 不可变集合&am…...
1. Flink自定义Source
一. Source 简介 DataStream是Flink的低级API,用于进行数据的实时处理,Flink编程模型分为Source、Transformation、Sink三个部分,如下图所示。 默认Flink提供了大量的内置Source,常见的Source如下: 基于文件的Sour…...
关于LinuxWindows双系统在八月更新后出现的问题
问题描述类似于:Verifying shim SBAT data failed: If you are, this is caused by a reported problem in the August update if you can get into Windows, either uninstall the August update, or open Command Prompt as administrator and run this command,…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
