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

算法笔记.kruskal算法求最小生成树

news 来源：原创 2025/5/24 9:07:50

题目：（来源：AcWing）

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

1≤n≤105,
1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过 1000。

输入样例：

输出样例：

kruskal算法思路：

每次联通一条最短边，加n-1次，如果边的两给节点已经联通，则无需再加。
查找两个点是否在同一个联通集合，需要用到并查集
如果加入边的数量<n-1，则说明无法生成最小生成树。

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;const int N = 100020,M = 200020;//定义边
struct Edge{int a,b,w;bool operator<(const Edge& edge){return w<edge.w;}
};int n,m;
int p[N];//并查集的集合
Edge edge[M];//边的集合int find(int x)//并查集的find函数
{if(p[x]!=x) p[x]=find(p[x]);//递归的同时压缩路径，提高效率return p[x];//直接返回所在集合编号
}int kruskal()
{int res=0,nums=0;//res记录最小树权和，num记录联通边数for(int i = 0;i<m;i++){Edge temp = edge[i];int a=temp.a , b=temp.b , c = temp.w;a = find(a);b = find(b);if(a != b)//a,b不在一个联通集合中{p[b] = a;//就把他们联通res+=c;//加入这个最短边nums++;//联通边数+1}}if(nums<n-1) return -1;return res;}int main()
{cin>>n>>m;for(int i = 1;i<=n;i++) p[i] = i;//初始化并查集for(int i = 0;i<m;i++)//初始化边集{int x,y,z;scanf("%d%d%d",&x,&y,&z);edge[i] = {x,y,z};}//边集升序排序sort(edge,edge+m);int t = kruskal();if(t==-1) cout <<"impossible"<<endl;else cout<<t<<endl;return 0;
}

参考：

B站@蓝不过海呀

地址：图-最小生成树-Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法_哔哩哔哩_bilibili

算法笔记.kruskal算法求最小生成树

题目：（来源：AcWing） 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。给定一张边带权的无向…...

编程日记 2025/5/24 9:07:50

量子算法调试：Grover算法搜索空间压缩过程可视化方案

一、Grover算法核心原理回顾 Grover算法通过以下两步迭代实现搜索空间压缩： Oracle操作（相位翻转）标记目标状态： Uω∣x⟩={−∣x⟩x=ω∣x⟩x≠ωUω∣x⟩={−∣x⟩∣x⟩x=ωx=ω 扩散操作（振幅放大）执行反转平均操作： D=2∣s⟩⟨s∣−ID=2∣s⟩⟨s∣−I 其…...

编程日记 2025/5/24 8:11:14

零基础搭建AI作曲工具：基于Magenta/TensorFlow的交互式音乐生成系统

引言：当AI遇见莫扎特 “音乐是流动的建筑”，当人工智能开始理解音符间的数学规律，音乐创作正经历着前所未有的范式变革。本文将手把手教你构建一套智能作曲系统，不仅能够生成古典钢琴小品，还能实现巴洛克与爵士风格的…...

编程日记 2025/5/24 8:16:22

springboot项目文件上传到服务器本机，返回访问地址

文件上传到服务器本机，然后给出访问地址： 具体如下： 1、添加必要的工具类依赖 <dependency><groupId>commons-fileupload</groupId><artifactId>commons-fileupload</artifactId>…...

编程日记 2025/5/24 5:20:42

mysql community 8.0.23升级到8.0.42再到8.4.5

近日生产服务器准备正式试运行，数据进入客户的专有网络，于是甲方派了人过来测漏洞，结果扫出一大堆。其间关于mysql的漏洞300多个，吓死人。给出的补丁地址，打开来看，全部是英文，可能是一些什么测…...

编程日记 2025/5/24 8:38:41

ubuntu安装docker，conda，tmux，btop，nvitop

在 Ubuntu 上安装 Docker Engine (使用华为云源) 1. 更新系统软件包 sudo apt update sudo apt upgrade -y2. 安装必要的依赖包 sudo apt install -y \ca-certificates \curl \gnupg \lsb-release \git \vim \wget3. 添加 Docker 的 GPG 密钥 (来自华为云镜像) # 创建用于存…...

编程日记 2025/5/24 8:26:33

大模型在肝硬化腹水风险预测及临床方案制定中的应用研究

目录一、引言 1.1 研究背景与意义 1.2 研究目的与创新点 1.3 研究方法与数据来源二、肝硬化及大模型相关理论基础 2.1 肝硬化概述 2.2 大模型技术原理 2.3 大模型在医疗领域的应用现状三、大模型预测肝硬化腹水术前风险 3.1 术前风险因素分析 3.2 大模型预测术前…...

编程日记 2025/5/24 8:45:58

孙宇晨将出席迪拜Token2049 与特朗普次子共话加密未来

据官方消息,波场TRON创始人孙宇晨将出席5月1日在迪拜举办的Token2049峰会上,并与特朗普次子埃里克特朗普(Eric Trump)进行一场备受瞩目的炉边对话,出席对话的人士还包括特朗普家族支持的去中心化金融项目WLFI(World Liberty Financial)的联合创始人Zach Witkoff。这场对话不仅彰…...

编程日记 2025/5/12 16:36:39

深入理解同源策略与跨域资源共享（CORS）

深入理解同源策略与跨域资源共享（CORS） 前言在当今的 Web 开发中，跨域资源请求已成为常见需求。然而，浏览器的同源策略（Same-Origin Policy）作为最基础的安全机制，限制了不同源之间的资源交互…...

编程日记 2025/5/18 10:44:15

Vue 生命周期钩子总结

Vue 生命周期钩子总结 Vue 组件的生命周期钩子允许在组件不同阶段执行自定义逻辑。以下是各阶段的钩子函数及其用途、触发时机和注意事项： 1. 生命周期阶段概览 Vue 组件的生命周期分为四个主要阶段： 创建（Creation）&#xff1…...

编程日记 2025/4/29 10:53:27

【解决方案】Linux解决CUDA安装过程中GCC版本不兼容

Linux解决CUDA安装过程中GCC版本不兼容目录问题描述解决方法安装后配置问题描述 Linux环境下安装 CUDA 时，运行sudo sh cuda_10.2.89_440.33.01_linux.run命令出现 “Failed to verify gcc version.” 的报错，提示 GCC 版本不兼容，查…...

编程日记 2025/4/29 10:52:23

网络准入控制系统推荐：2025年构建企业网络安全的第一道防线

随着信息技术的飞速发展，企业网络环境日益复杂，阳途网络准入控制系统作为一种先进的网络安全解决方案，其核心是确保网络接入的安全性。一、网络准入控制系统的基本原理与功能网络准入控制以“只有合法的用户、安全的终端才可以接入网络”为…...

编程日记 2025/5/15 20:23:21

AI Agent

李宏毅：从零开始搞懂 AI Agent - 知乎台大李宏毅2025 AI Agent新课来了！ - 知乎读懂AI Agent：基于大模型的人工智能代理 - 知乎 1.什么是AI Agent 一个基于大模型的 AI Agent 系统可以拆分为大模型、规划、记忆与工具使用四个组件部分。AI A…...

编程日记 2025/5/23 19:38:40

大模型如何应对内容安全：原理、挑战与技术路径探讨

随着大语言模型（LLM）技术的广泛应用，从AI写作助手到智能客服、再到生成式内容平台（AIGC），AI 正以前所未有的速度深入人类社会的各个角落。然而，随之而来的内容安全问题也日益凸显：模…...

编程日记 2025/4/29 10:52:18

Flinkcdc 实现 MySQL 写入 Doris

Flinkcdc 实现 MySQL 写入 Doris Flinkcdc 实现 MySQL 写入 Doris 一、环境配置 Doris：3.0.4 JDK 17 MySQL （业务数据库）：5.7 MySQL（本地数据库）：5.7 Flink：flink-1.19.1 flinkc…...

编程日记 2025/5/24 8:36:58

vim粘贴代码格式错乱排版错乱缩进错乱解决方案

从IDE复制代码, 粘贴到vim打开的文件出现以下格式错乱解决方案在使用 Vim 编辑器粘贴代码时，出现格式错乱的问题，通常是因为 Vim 的自动缩进功能与粘贴的代码发生了冲突。Vim 默认会尝试对输入的内容进行自动缩进，这会导致粘贴的代码被错误…...

编程日记 2025/5/24 8:38:41

发那科机器人（基本操作、坐标系、I/O通信）

发那科机器人（基本操作、坐标系、I/O通信）一，机器人基本操作1，坐标系种类2，机器人手动操作一关节运动3，机器人手动操作一直角运动二，坐标系建立1，工具坐标系建立原理及验证方法2，工具坐标系建立步骤3，用户坐标系建立原理及验证方法4，用户坐标系建立步骤三，I/O通信…...

编程日记 2025/5/24 8:29:58

GPU 架构入门笔记

引文位置：https://www.trainy.ai/blog/gpu-utilization-misleading 相关概念是通过 ChatGPT 迅速学习总结而成。概念： GPU H100 GPU, with 144 SMs 每个 SM（streaming multiprocessors） 的架构： GPU Utilizati…...

编程日记 2025/5/24 8:45:58

centos7使用yum快速安装Docker环境

一、基础环境设置 1：关闭防火墙和内核安全机制 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 02：配置网络yum源 [rootlocalhost ~]# curl -o /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Cento…...

编程日记 2025/4/29 10:46:53

解密面试高频题：加权轮询负载均衡算法 (Java 实现)

在分布式系统设计和面试中，负载均衡是一个绕不开的话题。而加权轮询（Weighted Round Robin, WRR）作为一种经典且实用的负载均衡策略，经常出现在笔试题和面试环节中。本文将带你深入理解 WRR 算法的原理，并探讨几种常见…...

编程日记 2025/5/11 21:03:28

Linux中的系统延时任务和定时任务与时间同步服务和构建时间同步服务器

延时任务在系统中我们的维护工作大多数时在服务器行对闲置时进行我们需要用延迟任务来解决自动进行的一次性的维护延迟任务时一次性的，不会重复执行当延迟任务产生输出后，这些输出会以邮件的形式发送给延迟任务发起者在RHEL9中默认系统中的所有普通…...

编程日记 2025/5/24 8:49:37

高效运维，智慧监测：COMEM光纤温度测量系统在电力行业中的应用

在电力行业中，变压器的稳定运行对于整个电网的安全很重要。为了确保变压器的健康状态，实时、精确的温度监测成为了不可或缺的一环。COMEM光纤温度测量系统应运而生，为变压器的温度监测提供了创新的解决方案。变压器温度监测的重要性变压器在…...

编程日记 2025/4/29 10:45:46

TP5兼容达梦国产数据库

1.首先数据库安装，部署时需配置大小写不敏感 2.安装PHP达梦扩展，一定要是对应版本（兼容操作系统）的扩展，否则会出现各种报错。参考官方文档：https://eco.dameng.com/document/dm/zh-cn/app-dev/php_php_new…...

编程日记 2025/5/24 2:56:34

[leetcode]2302.统计得分小于k的子数组

1.题目 2.事例 3.数据规模 4.思路（滑动窗口） 4.1滑动窗口的定义滑动窗口是一种在数组、字符串等序列数据结构上进行操作的算法技巧。以下是其定义及相关要素的详细介绍： 定义：滑动窗口可以理解为在一个序列上，用一…...

编程日记 2025/5/18 1:52:45

Linux网络编程：TCP多进程/多线程并发服务器详解

Linux网络编程：TCP多进程/多线程并发服务器详解 TCP并发服务器概述在Linux网络编程中，TCP服务器主要有三种并发模型： 多进程模型：为每个客户端连接创建新进程多线程模型：为每个客户端连接创建新线程I/O多路复用&am…...

编程日记 2025/5/15 13:44:29

Nacos源码—1.Nacos服务注册发现分析二

大纲 1.客户端如何发起服务注册发送服务心跳 2.服务端如何处理客户端的服务注册请求 3.注册服务—如何实现高并发支撑上百万服务注册 4.内存注册表—如何处理注册表的高并发读写冲突 2.服务端如何处理客户端的服务注册请求 (1)客户端自动发送服务注册请求梳理 (2)Nacos…...

编程日记 2025/4/29 10:44:41

设备指纹护航电商和金融反欺诈体系建设

众所周知，人的指纹具有唯一性，可以作为人的身份识别标识。对于设备而言，也有可以用于识别的特征。设备指纹是指可以用于唯一标识出某一设备的特征或者独特的设备标识，具有固定性、较难篡改性、唯一性等特质。设备指纹是金融机构…...

编程日记 2025/5/4 10:54:06

FFmpeg源码学习---ffmpeg

1、ffmpeg源码主函数 ┌────────────────────┐ │ main() │ └─────────┬───────────┘ ↓ ┌────────────────────┐ │ 初始化 (日志/网络等) │ │ init_dynload() │ │ avf…...

编程日记 2025/4/29 10:44:39

leetcode 206. 反转链表

题目描述： 迭代法： /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode …...

编程日记 2025/4/29 10:44:37

NVIDIA新模型DAM-3B：描述一切，图像视频局部描述新突破

在数字时代，图像和视频内容爆炸式增长，如何让AI像人类一样精准描述画面中的特定区域，成为计算机视觉领域的核心挑战。传统模型要么丢失细节，要么缺乏上下文，而NVIDIA与UC Berkeley联合团队提出的DAM（Descri…...

编程日记 2025/4/29 10:44:36

7、langChain和RAG实战：基于LangChain和RAG的常用案例实战

PDF 文档问答ChatBot 本地上传文档支持 pdf支持 txt支持 doc/docx问答页面 python环境新建一个requirements.txt文件streamlit python-docx PyPDF2 faiss-cpu langchain langchain-core langchain-community langchain-openai然后安装相应的包pip install -r requirements.t…...

编程日记 2025/4/29 10:43:34

c++11：类型转换

目录一 C语言中的类型转换二 . C强制类型转换 1. static_cast 2. reinterpret_cast 3. const_cast 4. dynamic_cast 三 explicit 关键字一 C语言中的类型转换在C语言中，如果赋值运算符左右两侧类型不同，或者形参与实参类型不匹配&#xff…...

编程日记 2025/4/29 10:43:33

Matlab自学笔记五十二：变量名称：检查变量名称是否存在或是否与关键字冲突

1.变量名称的命名规则有效的变量名称以字母开头，后跟字母、数字或下划线，Matlab变量名称对字母大小写是区分的，A和a是不相同的变量，不能使用与Matlab关键字冲突的变量名称，例如if、end等，判断一个字符是不…...

编程日记 2025/4/29 10:43:31

西门子PLC结构化编程_水处理系统水泵多备多投

文章目录前言一、功能概述二、程序编写1. 需求分析2. 编写运行时间累计功能块3. 创建自定义数据类型1. 时间排序数据类型2. 多备多投数据类型3. 多备多投切换数据类型 4. 编程1. 创建DB数据块1. 多备多投数据块2. 多备多投切换数据块 2. 创建FB功能块三、程序调用总结前言 …...

编程日记 2025/5/15 13:01:05

AutoGen 框架深度解析：构建多智能体协作的事件驱动架构

在当下多智能体（Multi-Agent）AI系统快速发展的背景下，AutoGen 作为微软研究院开源的编程框架，为构建可扩展、灵活且可调试的智能体协作应用提供了完备的工具与最佳实践。本文将从设计动机、核心架构、关键概念、安装与快速上手、典型场景、进阶特性、生态与扩展、最佳实践，…...

编程日记 2025/4/29 10:42:28

算法相关概念

1 算法概述 1.1 算法概念算法是特定问题求解步骤的描述，也是独立存在的一种解决问题的思想和方法对于算法而言，实现他的编程语言无关紧要，重要的是思想和方法！！！ 公式：程序算法数据结构&a…...

编程日记 2025/4/29 10:42:26

《Astro 3.0岛屿架构让内容网站“脱胎换骨”》

内容优先的网站越来越成为主流。无论是新闻资讯、知识博客，还是电商产品展示，用户都希望能快速获取所需内容，这对网站的性能和体验提出了极高要求。而Astro 3.0的岛屿架构，就像是为内容优先网站量身定制的一把神奇钥匙&#xff0c…...

编程日记 2025/5/15 6:31:20

Vue3 + Element-Plus + 阿里云文件上传

Element-Plus 阿里云文件上传 1、选择文件夹方法2、Chrome 浏览器查看 input typefile 元素上传的文件方法3、上传文件4、FormDataFormData 是什么创建 FormDataFormData 常用方法FormData 的实际应用性能与注意事项总结 1、选择文件夹方法 input typefile 元素想要上传文件夹…...

编程日记 2025/4/29 10:41:22

【Linux】第十一章管理网络

目录 1.TCP/IP网络模型物理层（Physical） 数据链路层（Date Link） 网络层（Internet） 传输层（Transport） 应用层（Application） 2. 对于 IPv4 地址&#…...

编程日记 2025/5/11 2:44:24

用vite动态导入vue的路由配置

在Vue应用中，通过路由可以实现不同页面之间的切换，同时也可以实现页面之间的传参和控制页面的显示与隐藏。但是我们在开发的过程中，会发现在路由配置中的路由配置和我们的项目结构高度重复，在我们修改页面文件结构时非常的麻烦与复…...

编程日记 2025/5/16 7:24:35

sources.list.d目录

sources.list可能大家很熟悉，是配置镜像链接的地方。 sources.list.d其实就是一个目录，在linux系统中.d后缀一般定义为一个目录，且很喜欢用这种方式。这种方式有一个好处，就是修改不会影响到sources.list文件， 在这里…...

编程日记 2025/5/18 11:14:41

【C语言】文件操作

目录一为什么使用文件二什么是文件程序文件数据文件文件名二进制文件和文本文件？ 三文件的打开与关闭流的概念标准流文件指针指针的声明指针的初始化四文件的打开与关闭打开 fopen()函数五总结： 前言： …...

编程日记 2025/4/29 10:40:16

静态库与动态库简介

静态库与动态库简介基本概念静态库静态库是在编译链接阶段被直接整合到可执行文件中的代码集合。链接器会从静态库中提取程序所需的所有对象，并将它们复制到最终的可执行文件中。特点： 可执行文件包含了所有代码，运行时无需外部依赖…...

编程日记 2025/4/29 10:38:09

02《小地图实时》Unity

创建一个新的项目创建一个球体作为主角重命名为Player 在主角上创建空的子物体重命名为MiniMapIcon 增加一个精灵图片并设置为绿色增加一个层（目的是在小地图中看的到而在场景中看不到这个绿色Icon） 命名为MiniMap 在主摄像机中设置剔除遮罩Culli…...

编程日记 2025/4/29 10:37:01

【Redis】基础4：作为分布式锁

文章目录 1. 一些概念2. MySQL方案2.1 方案一：事务特性2.1.1 存在的问题2.1.2 解决方案 2.2 方案二：乐观锁2.3 方案三：悲观锁 3. Redis3.1 实现原理3.2 实现细节3.2.1 问题1：持有期间锁过期问题3.2.2 问题2：判断和释放…...

编程日记 2025/5/21 4:05:52

迭代器与生成器

目录 Iterator 的作用 Iterator 的遍历过程 Symbol.iterator方法实现iterator接口的自定义类示例 Generator函数迭代器对象的next方法的运行逻辑迭代器对象除了具有next方法，还可以具有return方法。 Iterator 的作用为各种数据结构，提供一个统…...

编程日记 2025/5/15 12:27:55

Python 实现的运筹优化系统数学建模详解(动态规划模型）

相关代码链接：https://download.csdn.net/download/heikediguoshinib/90713747?spm1001.2014.3001.5503 一、引言在计算机科学与数学建模的广阔领域中，算法如同精密的齿轮，推动着问题的解决与系统的运行。当面对复杂的优化问题时&…...

编程日记 2025/5/19 13:31:19

miniconda在ARM64位芯片上面的安装

文章目录前言一、特点二、适用场景三、下载安装及使用1.下载脚本文件2.安装命令3.常见用法总结前言 Miniconda 是一个轻量级的 Python 发行版，它是 Anaconda 的一个简化版本。Anaconda 是一个广泛使用的数据科学平台，包含了众多的 Python 包和工具&a…...

编程日记 2025/5/6 1:58:01

vue跨域问题总结笔记

目录一、Websocket跨域问题 1.nginx配置 2.VUE CLI代理 3.env.development配置 4.nginx日志 5.解决一、解决跨域的几种常用方法 1.Vue CLI代理 2.JSONP 3.WebSocket 4.NGINX解决跨域问题 6.Java解决跨域二、Vue跨域问题详解 1. 什么是跨域 2. 跨域的例子 3.…...

编程日记 2025/5/20 12:21:43

自动驾驶领域专业词汇（专业术语）整理

以下是分类整理的自动驾驶领域专业词汇表，涵盖 AI、芯片、传感器、自动驾驶核心、辅助驾驶、安全、通信、车灯、泊车、测试标准等类别： AI相关缩写英文全称中文解释AIArtificial Intelligence人工智能，模拟人类智能的技术体系NNNeural Ne…...

编程日记 2025/5/22 20:28:12