【代码随想录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,…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...

《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...