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

[图论]Kruskal

news 来源：原创 2025/8/21 9:08:07

Kruskal

本质：贪心，对边进行操作。
存储结构：边集数组。
适用对象：可为负权图，可求最大生成树。
核心思想：最短的边一定在最小生成树(MST)上，对最短的边进行贪心。
算法流程：对全体边集 $\set{E}$ 由小到大排序。遍历所有边，每次添加使已选边集不成环的边，直到已选 $V - 1$ 条边。可使用并查集判环，每次加边前先判断两点是否同属一个集合，每次加边时将两点合并到一个集合。
复杂度： $O(E\log_2E)$

注：若无特殊说明，本文顶点与边编号均从0开始。

数据结构定义

using ll=long long;
ll n,m,s;//点数,边数,源点
struct edge{int u,v,w;
}e[m];
bool cmp(edge a,edge b){return a.w<b.w;
}
int s[n];
int Find(int x){if(s[x]!=x) s[x]=Find(s[x]);return s[x];
}
void init(){for(int i=0;i<n;i++) s[i]=i;
}

实现

int kruskal(){sort(e,e+m,cmp);init();int ans=0,cnt=0;for(int i=0;i<m;i++){if(cnt==n-1) break;int U=e[i].u,V=e[i].v,W=e[i].w;int u1=Find(U),u2=Find(V);if(u1==u2) continue;//成环,不选当前边else{ans+=W;s[u1]=u2;//合并到一个集合cnt++;}}if(cnt==n-1) return ans;return -1;
}

若求最大生成树，改为对边集 $\set{E}$ 由大到小排序即可。

[图论]Kruskal

Kruskal 本质：贪心，对边进行操作。存储结构：边集数组。适用对象：可为负权图，可求最大生成树。核心思想：最短的边一定在最小生成树(MST)上，对最短的边进行贪心。算法流程：对全体边集…...

编程日记 2025/8/21 9:08:07

腾讯云对象存储以及项目业务头像上传

腾讯云上传步骤： service-vod模块化中 ①、参考文档，引入依赖 ②、配置文件application.properties ③、创建工具类初始化bean的时候读取配置文件 Component public class ConstantPropertiesUtil implements InitializingBean{Value("${t…...

编程日记 2025/8/20 4:48:53

Windows下导入文件中的环境变量

在Windows批处理脚本（.bat）中，通过文件获取并设置环境变量通常涉及逐行读取文件内容并动态赋值给变量。以下是具体实现方法及示例： 一、从文件读取变量并设置到环境变量假设有一个配置文件（如env_config.txt&#xf…...

编程日记 2025/8/17 18:21:29

【音视频开发】第五章 FFmpeg基础

【音视频开发】第五章 FFmpeg基础文章目录【音视频开发】第五章 FFmpeg基础一、播放器框架1.媒体文件读取阶段2.音频处理流程3.视频处理流程二、常用音视频概念1.常用音视频术语2.复用器3.编解码器三、FFmpeg 库1.整体结构四、FFmpeg 常用函数1.libavformat 封装/解封装2.…...

编程日记 2025/8/21 2:34:07

【ESP32|音频】一文读懂WAV音频文件格式【详解】

简介最近在学习I2S音频相关内容，无可避免会涉及到关于音频格式的内容，所以刚开始接触的时候有点一头雾水，后面了解了下WAV相关内容，大致能够看懂wav音频格式是怎么样的了。本文主要为后面ESP32 I2S音频系列文章做铺垫&#xff0…...

编程日记 2025/8/17 18:24:50

数据通信学习笔记之OSPF路由汇总

区域间路由汇总路由汇总又被称为路由聚合，即是将一组前缀相同的路由汇聚成一条路由，从而达到减小路由表规模以及优化设备资源利用率的目的，我们把汇聚之前的这组路由称为精细路由或明细路由，把汇聚之后的这条路由称为汇总路由或…...

编程日记 2025/8/17 18:21:14

【C++】priority_queue的底层封装和实现

目录前言基本结构如何设置默认大小堆底层实现仿函数的使用向上调整算法向下调整算法其他接口 end 前言 priority_queue的介绍优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priorit…...

编程日记 2025/8/20 8:28:10

2023年全国青少年信息素养大赛 Python编程挑战赛小学全年级组初赛真题答案详细解析

2023信息素养大赛 Python编程挑战赛选择题（共15题，每题5分，共75分） 1、关于列表的索引，下列说法正确的是 A、列表的索引从0开始 B、列表的索引从1开始 C、列表中可能存在两个元素的索引一致 D、列表中索引的最大…...

编程日记 2025/8/20 11:25:02

十三种通信接口芯片——《器件手册--通信接口芯片》

目录通信接口芯片简述基本功能常见类型应用场景详尽阐述 1 RS485/RS422芯片 1. RS485和RS422标准 2. 芯片功能 3. 典型芯片及特点 4. 应用场景 5. 设计注意事项 6. 选型建议 2 RS232芯片 1. RS232标准 2. 芯片功能 3. 典型芯片及特点 4. 应用场景 5. 设计注意事项 6…...

编程日记 2025/8/17 18:27:36

PyTorch生成式人工智能实战（1）——神经网络与模型训练过程详解

PyTorch生成式人工智能实战（1）——神经网络与模型训练过程详解 0. 前言1. 传统机器学习与人工智能2. 人工神经网络基础2.1 人工神经网络组成2.2 神经网络的训练 3. 前向传播3.1 计算隐藏层值3.2 执行非线性激活3.3 计算输出层值3.4 计算损失值3.5 实现前…...

编程日记 2025/8/18 19:04:24

【软件系统架构】事件驱动架构

一、引言在当今的软件开发和系统架构领域，事件驱动架构（Event - Driven Architecture，EDA）正逐渐成为构建复杂、分布式和可扩展系统的热门选择。随着信息技术的不断发展，传统的架构模式在应对高并发、实时性要求高、数…...

编程日记 2025/8/19 16:53:53

Doris FE 常见问题与处理指南

在数据仓库领域，Apache Doris 凭借其卓越性能与便捷性被广泛应用。其中，FE（Frontend）作为核心组件，承担着接收查询请求、管理元数据等关键任务。然而，在实际使用中，FE 难免会遭遇各类问题&#…...

编程日记 2025/8/17 18:21:15

Manus AI “算法-数据-工程“三位一体的创新

Manus AI在多语言手写识别领域的技术突破，通过算法创新、数据工程与场景适配的协同作用，解决了传统手写识别的核心痛点。以下是其关键技术路径与创新点的系统性分析： 一、深度学习模型与算法优化混合神经网络架构Manus AI采用"CNN与LST…...

编程日记 2025/8/21 8:29:17

Flutter Expanded 与 Flexible 详解

目录 1. 引言 2. Expanded 的基本用法 3. Flexible 的基本用法 4. Expanded vs Flexible 的区别 4.1 基础定义 4.2 关键差异 5. Expanded 深度解析 5.1 按比例分配 5.2 强制填充特性 6. Flexible 深度解析 6.1 基础用法：动态收缩 6.2 结合 fit 参数控制…...

编程日记 2025/8/17 18:21:16

乘用车制动系统设计：保障行车安全的核心技术

摘要随着汽车工业的快速发展，乘用车制动系统的设计至关重要。本文详细阐述了乘用车制动系统的工作原理、组成部分、常见类型，深入分析了制动系统设计过程中的关键要点，包括制动力分配、制动管路设计、制动助力系统选型等。同时，…...

编程日记 2025/8/17 18:27:03

电力行业在保障用电安全方面正积极采用先进的物联网技术

电力行业在保障用电安全方面正积极采用先进的物联网技术电力行业的物联网安全用电监管装置正发挥着至关重要的作用。 ASCO 电不着安全用电装置凭借其卓越的性能，成为了解决用电安全问题的得力助手。当电漏电这种危险情况悄然发生时，物联网 ASCO 电不着…...

编程日记 2025/8/17 18:25:25

TDengine 语言连接器（PHP）

简介 PHP 语言广泛用于 Web 开发的开源脚本语言。它语法简单，容易学习，既支持面向过程，也支持面向对象编程。具有跨平台性，能与多种数据库交互，可与 HTML 等前端技术配合，动态生成网页内容。常用于开发各类…...

编程日记 2025/8/17 18:28:22

使用docker该怎么做：从公有仓库拉取镜像并上传到私有仓库

在容器化部署中，将公有镜像仓库（如Docker Hub）的镜像迁移到私有仓库（如Harbor、Nexus）是常见需求。一、为什么需要将镜像从公有仓库传到私有仓库？ 网络连通性：公有仓库依赖公网访问&#xff…...

编程日记 2025/8/17 18:22:14

list的使用

1：list文档 list文档在之前我们对于链表有过最初始的模拟实现，现在进入C之后，我们可以在STL库中发现到链表这个容器的使用，list的底层也是我们最初实现的双向链表。 2：list的使用 list的接口有很多，我们…...

编程日记 2025/8/20 3:58:06

Redis遇到Hash冲突怎么办

在 Redis 中，哈希冲突通常是指当多个键的哈希值相同或位于相同的哈希槽中时发生冲突。Redis 通过底层的哈希表和一些冲突解决机制（如开放地址法、链表法等）来处理哈希冲突问题。这些通常是透明的，作为开发者，我们无需直…...

编程日记 2025/8/17 21:03:23

OpenCV 图形API（42）颜色空间转换-----将 BGR图像转换为 I420（YUV 4:2:0）格式函数BGR2I420()

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述将图像从BGR色彩空间转换为I420色彩空间。该函数将输入图像从BGR色彩空间转换为I420。R、G和B通道值的传统范围是0到255。输出图像必须是8位无…...

编程日记 2025/8/20 4:26:11

简述Apache RocketMQ

整体架构分析基本流程模块特性发送消息流程原理分析同步发送 sync 异步发送 async 直接发送 one-way 主从同步（HA）机制分析消息投递持久化机制 RocketMQ的RPC通信 RocketMQ中Remoting通信模块的具体实现消息的协议涉及与编码解码消…...

编程日记 2025/8/19 21:15:20

AI融合SEO关键词实战指南

内容概要随着人工智能技术的迭代升级，SEO关键词策略正经历从人工经验驱动向数据智能驱动的范式转变。本指南聚焦AI技术在搜索引擎优化中的系统性应用，通过构建多层技术框架实现关键词全生命周期管理。核心方法论涵盖语义分析引擎的构建原理、基于NLP的…...

编程日记 2025/8/17 18:22:34

RK3588 实现音视频对讲

RK3588 实现音视频对讲方案 RK3588是瑞芯微推出的一款高性能处理器，非常适合用于音视频对讲系统的开发。以下是基于RK3588实现音视频对讲的方案概述： 硬件架构核心处理器：RK3588 (4xCortex-A76 4xCortex-A55)视频处理： 内置8…...

编程日记 2025/8/20 8:24:22

OSPF区域间路由计算

ABR：区域边界路由器，连接两个不同区域的设备就称为ABR（不同厂商不同，定义很模糊） ASBR：自治系统边界路由器，引入了外部路由，将不是自治系统外部的不是OSPF路由的条目变成OSPF路由条目…...

编程日记 2025/8/20 5:57:02

NAT、代理服务、内网穿透

NAT、代理服务、内网穿透 1、NAT1.1、NAT过程1.2、NAPT2、内网穿透3、内网打洞3、代理服务器3.1、正向代理3.2、反向代理1、NAT 1.1、NAT过程之前我们讨论了IPv4协议中IP地址数量不充足的问题。NAT技术是当前解决IP地址不够用的主要手段，是路由器的一个重要功能。 NAT能够将…...

编程日记 2025/8/17 18:26:36

阿尔特拉 EP1C12F324I7N AlteraFPGA Cyclone

EP1C12F324I7N 属于 Altera Cyclone I 系列 FPGA 中的中低密度型号，面向成本敏感、功耗受限的嵌入式与数据通路应用。该器件采用 0.13 μm 全层铜 SRAM 工艺，集成约 12 060 个逻辑单元（LE）、239 616 位片上 RAM、249 路可编…...

编程日记 2025/8/20 9:37:57

解决“驱动程序无法通过使用安全套接字层(SSL)加密与 SQL Server 建立安全连接“问题

参考链接: https://blog.csdn.net/yyj12138/article/details/123073146...

编程日记 2025/8/17 20:28:11

QtApplets-实现应用程序单例模式，防止重复运行

QtApplets-实现应用程序单例模式，防止重复运行文章目录 QtApplets-实现应用程序单例模式，防止重复运行摘要引言实现原理核心代码实现头文件定义实现文件使用方法技术要点解析1. 文件锁机制2. 进程 ID 管理3. Windows 互斥量4. 跨平台兼容注意事项…...

编程日记 2025/8/17 18:26:23

nodejs使用pkg打包文件

pkg配置 "pkg": {"assets": ["*.html","*.css","*.js"],"mirror": "https://npmmirror.com/mirrors/node-v8-compile-cache/"},"bin": "server.js",嵌入到exe中的资源使用assets打…...

编程日记 2025/8/20 20:19:48

学习笔记十六——Rust Monad从头学

🧠 零基础也能懂的 Rust Monad：逐步拆解三大定律通俗讲解实战技巧 📣 第一部分：Monad 是什么？ Monad 是一种“包值链操作保持结构”的代码模式，用来处理带上下文的值，并方便连续处理。 …...

编程日记 2025/8/18 14:30:13

Idea连接远程云服务器上的MySQL，开放云服务器端口

1.开放云服务器的3306端口 （1）进入到云服务器的控制台 （2）点击使用的云服务器 （3）点击配置安全组规则 （4）添加规则 （5）开放端口 2.创建可以远程访问…...

编程日记 2025/8/20 2:06:46

云服务器CVM标准型S5实例性能测评——2025腾讯云

腾讯云服务器CVM标准型S5实例具有稳定的计算性能，CPU采用采用 Intel Xeon Cascade Lake 或者 Intel Xeon Cooper Lake 处理器，主频2.5GHz，睿频3.1GHz，CPU内存配置2核2G、2核4G、4核8G、8核16G等配置，公网带宽可选1M、3…...

编程日记 2025/8/20 22:43:28

【Pytorch之一】--torch.stack()方法详解

torch.stack方法详解 pytorch官网注释 Parameters tensors：张量序列，也就是要进行stack操作的对象们，可以有很多个张量。 dim：按照dim的方式对这些张量进行stack操作，也就是你要按照哪种堆叠方式对张量进行堆叠。dim的…...

编程日记 2025/8/20 13:05:13

监控+日志=DevOps 运维的“千里眼”与“顺风耳”

监控+日志=DevOps 运维的“千里眼”与“顺风耳” 在 DevOps 体系中，监控和日志管理是不可或缺的运维基石。有人说，开发只管把代码写好，运维才是真正的“操盘手”，让系统稳定运行、不宕机、不崩溃。而要做到这一点，精准的监控与日志管理是关键。试想一下：如果没有监控…...

编程日记 2025/8/20 13:26:35

实战｜使用环信Flutter SDK构建鸿蒙HarmonyOS应用及推送配置

本文为大家介绍如何在 Flutter 环境创建 Harmony 项目并集成环信即时通讯IM以及环信 Flutter Harmony 推送配置。已经基于环信的 Flutter 项目也可以参考本文适配鸿蒙端。一、开发环境要求前置条件 1.安装DevEco-Studio 2.安装模拟器 DevEco-Studio 下载与操作指导&…...

编程日记 2025/8/17 18:21:30

构建知识体系

我认为，仅仅建立知识点之间的连接还不足够，还要建立自己的知识体系。那么什么是知识体系呢？ 知识体系，可以理解为立体的知识系统。立体的知识系统，代表着跨越了多个领域、行业、学科的知识，是多个层面…...

编程日记 2025/8/20 18:59:46

Android Mainline简介

关键要点 Android Mainline 是通过模块化更新 Android 核心组件的框架，可能提高安全性。允许通过 Google Play 系统更新分发模块，无需完整固件更新。能简化厂商工作并减少碎片化，但覆盖范围有限。什么是 Android Mainline？ And…...

编程日记 2025/8/21 7:26:19

2026《数据结构》考研复习笔记二（C++面向对象）

C面向对象一、类二、继承三、重载运算符和重载函数四、多态代码示例一、类 1.1类&对象 class classname//class是关键词，classname是类名 { Access specifiers://访问修饰符：private/public/protected Date members/variables;//变量 Member fun…...

编程日记 2025/8/21 8:09:14

【C++】12.list接口介绍

在C标准库中，std::list 是一个基于双向链表实现的顺序容器，它支持高效的插入和删除操作，但无法直接通过下标进行随机访问。以下是关于 std::list 的简单介绍： 核心特性底层结构双向链表实现，每个节点包含数据、前驱指…...

编程日记 2025/8/21 2:34:12

决策卫生问题：考公考编考研能补救高考选取职业的错误吗

对于决策者来说，“认识你自己”是一个永恒的主题；警惕认知中的缺陷，比什么都重要。在判断与决策问题上，管理者和专业人士往往都非常自信。人类远远不如我们想象的那么理性，人类的判断也远远不如我们想象的那么完美。在…...

编程日记 2025/8/19 7:13:57

考研系列-计算机网络-第一章、计算机网络体系结构

一、计算机网络概述 1.知识点总结性能指标： 注意这个指标： 2.习题总结 (一)选择题广域网点对点，局域网广播技术 (二)简答题 (1)概念性题目： (2)计算型题目这个题目主要是注意两种交换方式： 电路交换：…...

编程日记 2025/8/17 19:07:44

状态模式：有限状态机在电商订单系统中的设计与实现

状态模式：有限状态机在电商订单系统中的设计与实现一、模式核心：用状态切换驱动行为变化在电商订单系统中，订单状态会随着用户操作动态变化：「已创建」的订单支付后变为「已支付」，发货后变为「已发货」&#xff0…...

编程日记 2025/8/16 23:43:17

nohup命令使用说明

文章目录如何在后台运行程序呢？如何正常运行代码重定向呢？nohup: ignoring input 如何在后台运行程序呢？ 使用nohup命令即可， nohup python dataset/ReferESpatialDataset.py >>dataset_20250417.log 2>&1 &n…...

编程日记 2025/8/17 18:28:07

使用原生button封装一个通用按钮组件

效果图代码 <script lang"ts" setup> import { computed, ref, watch } from "vue";/*** 按钮属性接口*/ interface ButtonProps {/** 按钮类型：default(默认)/dark/plain/link */type?: "default" | "dark" | &q…...

编程日记 2025/8/21 4:48:35

osu ai 论文笔记 DQN

e https://theses.liacs.nl/pdf/2019-2020-SteeJvander.pdf Creating an AI for the Rhytm Game osu! 20年的论文用监督学习训练移动模型100首歌能达到95准确率点击模型用DQN两千首歌65准确率 V抖用的居然不是强化学习？ 5,6星打96准确度还是有的东西的这是5.…...

编程日记 2025/8/20 8:11:54

perf的架构 1.perf event event are pure kernel counters, in this case they are called software events. Examples include: context-switches, minor-faults.events is the processor itself and its Performance Monitoring Unit (PMU). It provides a list of events …...

编程日记 2025/8/17 19:58:35

Kruskal

数据结构定义

实现

相关文章：