代码随想录算法训练营第六十二天| prim算法,kruskal算法
训练营六十二天打卡,图论比较难,坚持下来胜利就在眼前!
53.卡码网【寻宝】
题目链接
解题过程
- 没做过类似的题目,跟着答案敲了一遍
- 最小生成树 可以使用 prim算法 也可以使用 kruskal算法计算出来。
- prim算法 是从节点的角度 采用贪心的策略 每次寻找距离 最小生成树最近的节点 并加入到最小生成树中。
- prim算法核心就是三步,prim三部曲:
- 第一步,选距离生成树最近节点
- 第二步,最近节点加入生成树
- 第三步,更新非生成树节点到生成树的距离(即更新minDist数组)
- minDist数组 用来记录 每一个节点距离最小生成树的最近距离。
prim算法
#include<iostream>
#include<vector>
#include<climits>
using namespace std;int main() {int v, e;cin >> v >> e;vector<vector<int>>grid(v + 1, vector<int>(v + 1, 10001));while (e--) {int x, y, val;cin >> x >> y >> val;grid[x][y] = grid[y][x] = val;}vector<int>minDist(v + 1, 10001);vector<bool>isInTree(v + 1, false);for (int i = 1; i < v; i++) { // v - 1条边int cur = -1;int minVal = INT_MAX;for (int j = 1; j <= v; j++) {if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}isInTree[cur] = true;for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}int result = 0;for (int i = 2; i <= v; i++) {result += minDist[i];}cout << result << endl;return 0;
}
- prim 算法是维护节点的集合,而 Kruskal 是维护边的集合。
- kruscal的思路:
- 边的权值排序,因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合,说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合,加入到最小生成树,并把两个节点加入同一个集合
- 将两个节点加入同一个集合,又如何判断两个节点是否在同一个集合呢
- 答案是并查集
- 并查集主要就两个功能:
- 将两个元素添加到一个集合中
- 判断两个元素在不在同一个集合
Kruskal算法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge{int l, r, val;
}; // l r 为边,val为边的数值
vector<int>father;
void init(int v) {father.resize(v + 1);for (int i = 0; i <= v; i++) {father[i] = i;}
}
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]);
}void join(int u, int v) {u = find(u);v = find(v);if (u != v) {father[v] = u;}
}int main() {int v, e;cin >> v >> e;init(v);vector<Edge>edges;while (e--) {int l, r, val;cin >> l >> r >> val;Edge edge;edge.l = l;edge.r = r;edge.val = val;edges.push_back(edge);}sort(edges.begin(), edges.end(), [](Edge& e1, Edge& e2)->bool{return e1.val < e2.val;});int result = 0;for (Edge edge : edges) {int x = find(edge.l);int y = find(edge.r);if (x != y) {result += edge.val;join(x, y);}}cout << result << endl;return 0;
}
相关文章:
代码随想录算法训练营第六十二天| prim算法,kruskal算法
训练营六十二天打卡,图论比较难,坚持下来胜利就在眼前! 53.卡码网【寻宝】 题目链接 解题过程 没做过类似的题目,跟着答案敲了一遍最小生成树 可以使用 prim算法 也可以使用 kruskal算法计算出来。prim算法 是从节点的角度 采用…...
Newstar_week1_week2_wp
week1 wp crypto 一眼秒了 n费马分解再rsa flag: import libnum import gmpy2 from Crypto.Util.number import * p 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297…...
今天我们研究一段代码(异或位运算)
let a 18 // 甲 let b 20 // 乙a a ^ b b a ^ b a a ^ b console.log("a",a) // a 20 console.log("b",b) // b 18今天我们就研究上面这一段代码,简单解释一下,初始化一个a 18 b 20, 中间经过了三次的异或之后…...
pycharm中使用ctrl+鼠标滚轮改变字体大小
文章目录 pycharm使用ctrl鼠标滚轮改变字体大小1.打开pycharm选择file2.选择setting4.选择keymap,然后再右边的输入框中输入increase进行增大字体4.鼠标选择后,点击添加鼠标快捷方式,然后设置鼠标滚轮往上增大字体。5.设置缩小字体࿰…...
【算法-动态规划】打家劫舍专题
文章目录 1.打家劫舍1.1一维数组1.2三变量法1.3双数组法 2.打家劫舍22.1双数组法2.2 三变量法 3.打家劫舍33.1动态规划3.2双变量法 4.删除相邻数字的最大分数4.1双状态数组4.2一维数组4.3三变量法 1.打家劫舍 198. 打家劫舍 - 力扣(LeetCode) 1.1一维数…...
关于技术管理者的一些思考
前 言 在软件开发领域,当一名资深工程师有机会成为一名技术管理者的时候,通常他/她的反应是什么?兴奋、担扰、无奈还是推托,具体是什么心情也许对结果并不重要,更加重要是在一刻,我们一定要问问我们内心的…...
Alpha-CLIP: A CLIP Model Focusing on Wherever You Want CVPR 2024
在原始的接受RGB三通道输入的CLIP模型的上额外增加了一个alpha通道。在千万量级的RGBA-region的图像文本对上进行训练后,Alpha-CLIP可以在保证CLIP原始感知能力的前提下,关注到任意指定区域。 GitHub - SunzeY/AlphaCLIP: [CVPR 2024] Alpha-CLIP: A CLI…...
Golang | Leetcode Golang题解之第495题提莫攻击
题目: 题解: func findPoisonedDuration(timeSeries []int, duration int) (ans int) {expired : 0for _, t : range timeSeries {if t > expired {ans duration} else {ans t duration - expired}expired t duration}return }...
04 go语言(golang) - 变量和赋值过程
变量 在Go语言中,变量的定义和初始化是编程的基础部分。Go提供了多种方式来声明和初始化变量,以适应不同的使用场景。 基本变量声明 使用var关键字: 使用var关键字可以在函数内部或外部声明变量。如果在函数外部声明,该变量为全…...
语言/图像/视频模型一网打尽!BigModel大模型开放平台助力开发者轻松打造AI新应用!
2024年8⽉28⽇,在ACM SIGKDD(国际数据挖掘与知识发现⼤会,KDD)上会议现场,智谱AI重磅推出了新⼀代全⾃研基座⼤模型 GLM-4-Plus、图像/视频理解模型 GLM-4V-Plus 和⽂⽣图模型 CogView3-Plus。这些新模型,已…...
Go语言Linux环境搭建以编写第一个Go程序
目录 文章目录 目录Go语言入门1、说明2、CentOS7安装Go3、编写第一个程序3.1、编写程序3.2、运行程序3.3、生成二进制文件4、编写第一个web程序4.1、编写代码4.2、运行程序4.3、测试访问4.4、生成二进制配置Vim-go语法高亮1)、下载和设置Vundle.vim(vim安装插件的工具)2)、…...
使用 Go 构建一个最小的 API 应用
最近有项目要使用 Go 开发,作为一个. NET Core 选手,准备先撸一个包含 CRUD 的最小 MVP 项目练手。 要创建一个 TODO 应用,会创建下面这些接口: APIDescriptionRequest bodyResponse bodyGET /todoitemsGet all to-do itemsNone…...
MySQL 日常维护指南:常见任务、频率及问题解决
MySQL 作为一种广泛使用的开源关系型数据库,随着数据量和应用复杂性的增加,定期的数据库维护对于保持系统高效运行至关重要。通过合理的日常维护,数据库管理员能够确保 MySQL 数据库的稳定性、性能以及数据的完整性。本文将介绍 MySQL 的常见…...
oracle ORA-24920:列大小对于客户机过大
问题描述 在一次读取某个视图数据过程中,当数据读取到x条时,报错ORA-24920:列大小对于客户机过大。 通过查询资料得知,oracle 数据库升级到了12c,VARCHAR2的容量也从4000升级到了32767。 所以猜测某个字段的长度超过4…...
使用 Docker compose 部署 Nacos(达梦数据库)
1. 制作镜像的源码地址 https://github.com/wangsilingwsl/nacos-dm.git 参考的开源项目:https://github.com/jeecgboot/JeecgBoot/tree/master/jeecg-boot/jeecg-server-cloud/jeecg-cloud-nacos (master分支;tag:v3.7.1&#…...
人工智能 | 阿里通义千问大模型
简介 通义千问系列模型为阿里云研发的大语言模型。千问模型基于 Transformer 架构,在超大规模的预训练数据上进行训练得到。预训练数据类型多样,覆盖广泛,包括大量网络文本、专业书籍、代码等。同时,在预训练模型的基础之上&…...
Windows环境下Qt Creator调试模式下qDebug输出中文乱码问题
尝试修改系统的区域设置的方法: 可以修复问题。但会出现其它问题: 比如某些软件打不开,或者一些软件界面的中文显示乱码! 暂时没有找到其它更好的办法。...
java防止表单重复提交的注解@RepeatSubmit
代码解释 RepeatSubmit 是一个自定义注解,通常用于防止表单重复提交。这个注解可以应用于控制器方法上,以确保同一个请求在一定时间内不会被多次提交。以下是一些常见的参数和用法: value: 注解的名称或描述。 interval: 两次请求之间的最小间…...
HTTP快速入门
HTTP报文结构 HTTP 协议主要由三大部分组成: ● 起始行(start line):描述请求或响应的基本信息; ● 头部字段(header):使用 key-value 形式更详细地说明报文; ● 消息正…...
Nacos简介
Nacos是一个开源的动态服务发现、配置管理和服务管理平台,由阿里巴巴集团开发并开源。它提供了服务注册与发现、配置管理、动态DNS服务、服务健康监测、权重和流量管理等核心特性,非常适合构建云原生应用和微服务架构。 Nacos的核心功能包括:…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
