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

经典算法最小生成树(prim算法)

news 来源：原创 2025/7/16 6:54:21

最小生成树

题目描述

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

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

给定一张边带权的无向图 G = (V, E)，其中：

V 表示图中点的集合，n = |V|
E 表示图中边的集合，m = |E|

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

输入格式

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

输出格式

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

c++代码

#include<bits/stdc++.h>using namespace std;struct edge{int a, b, val;
};struct mycmp{bool operator()(const edge& a, const edge& b) { return a.val > b.val; }
};int main() {int n, m, a, b, c;edge e;cin >> n >> m;vector<vector<edge>> edges(n + 1);for (int i = 0; i < m; i++) {cin >> a >> b >> c;e.a = a, e.b = b, e.val = c, edges[a].push_back(e);e.b = a, e.a = b, edges[b].push_back(e);}priority_queue<edge, vector<edge>, mycmp> q;vector<bool> vis(n + 1, false);vector<edge> ans;int start = 1;for (int i = 0; i < n - 1; i++) {vis[start] = true;for (edge x : edges[start]) if (!vis[x.b]) q.push(x);while(!q.empty() && vis[q.top().b]) q.pop();if (q.empty()) {cout << -1;return 0;}e = q.top(), ans.push_back(e), q.pop(), start = e.b;}int sum = 0;for (edge x : ans) sum += x.val;cout << sum;return 0;
}

经典算法最小生成树(prim算法)

最小生成树题目描述给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和。如果最小生成树不存在，则输出 impossible。给定一张边带权的无向图 G (V, E)，其中&#xff1a…...

编程日记 2025/7/16 6:54:21

机器学习中的分类和回归问题

1. 分类问题机器学习中的分类问题是一种监督学习任务，其核心目标是将数据样本分配到预定义的离散类别中，例如判断邮件是否为垃圾邮件、识别图像中的物体类型等。分类通过已知标签的训练数据（如带类别标注的样本）学习特征与类别…...

编程日记 2025/6/29 7:55:31

安装&卸载 -- 安装numpy pip install numpy1.26.4 -- 从索引安装（自定义源） pip install package_name --index-url https://custom_url -- 安装本地文件或目录 pip install /path/to/package.whl pip install D:\Downloads\transformers-4.40.0-py…...

编程日记 2025/7/16 6:03:12

n8n工作流自动化平台的实操：Cannot find module ‘iconv-lite‘

解决问题： 1.在可视化界面，执行const iconv require(iconv-lite);，报Cannot find module iconv-lite [line 2]错误； 查看module的路径进入docker容器 #docker exec -it n8n /bin/sh 构建一个test.js,并写入如何代码 vi tes…...

编程日记 2025/7/16 6:23:39

AIGC时代——语义化AI驱动器：提示词的未来图景与技术深潜

文章目录一、技术范式重构：从指令集到语义认知网络1.1 多模态语义解析器的进化路径1.2 提示词工程的认知分层二、交互革命：从提示词到意图理解2.1 自然语言交互的认知进化2.2 专业领域的认知增强三、未来技术图谱：2025-2030演进路线3.1 20…...

编程日记 2025/6/28 20:04:43

基于Springboot高校网上缴费综合务系统【附源码】

基于Springboot高校网上缴费综合务系统效果如下： 系统登陆页面个人中心页面论坛交流页面发表评论页面付款页面教师缴费页面新增缴费类型页面审核页面研究背景随着高校信息化建设进程的加速，传统手工缴费模式因效率低、错误率高、管理成本高…...

编程日记 2025/6/29 5:45:45

返回倒数第k个节点题解

这题要用到快慢指针的思想。 1.定义两个指针，一个快指针，一个慢指针，初始都指向头结点 2.先让快指针往后走k步，也就是移动k个节点，这个时候快指针比慢指针领先k 3.现在让快慢指针同时往后移动，两指针之间…...

编程日记 2025/6/29 6:34:40

《操作系统精髓与设计原理》第4章课后题答案-线程、对称多处理器和微内核

1.表3.5列出了在一个没有线程的操作系统中进程控制块的基本元素。对于多线程系统，这些元素中哪些可能属于线程控制块，哪些可能属于进程控制块？ 对于不同的系统来说通常是不同的，但一般来说，进程是资源的所有者&#xf…...

编程日记 2025/6/29 5:13:23

《ATPL地面培训教材13：飞行原理》——第4章：亚音速气流

翻译：刘远贺；工具：Cursor & Claude 3.7；过程稿第4章：亚音速气流目录翼型术语气流基础二维气流总结习题答案翼型术语翼型一种能够以较高效率产生升力的特殊形状。弦线连接翼型前缘和后缘曲率中心的直…...

编程日记 2025/7/14 16:51:08

5月3日星期六今日早报简报微语报早读

5月3日星期六，农历四月初六，早报#微语早读。 1、五一假期多地政府食堂对外开放：部分机关食堂饭菜“秒没”； 2、2025年五一档电影新片票房破3亿； 3、首日5金！中国队夺得跳水世界杯总决赛混合团体冠军&…...

编程日记 2025/6/29 8:18:45

2024 虚拟电厂与大电网三道防线的关系探讨【附全文阅读】

本文围绕虚拟电厂与大电网三道防线展开探讨。大电网三道防线包括第一道防线的预防性控制和继电保护、第二道防线的稳控系统、第三道防线的失步解列及频率电压紧急控制装置 ，新型电力系统建设对第三道防线带来频率稳定等挑战。当前新型配电网第三道防线建设存在问题&…...

编程日记 2025/7/10 8:22:38

【c++】模板详解

目录泛型编程模板的使用函数模板函数模板的本质函数模板的实例化显式实例化隐式实例化函数模板的模板参数的匹配原则类模板类模板的本质类模板的实例化非类型模板参数模板特化函数模板特化类模板特化类模板全特化类模板偏特化（半特化） 模板分离编译t…...

编程日记 2025/6/29 8:16:05

【Linux】驱动开发方法

使用Petalinux学习驱动开发时的一些经验。部分图片和经验来源于网络，若有侵权麻烦联系我删除，主要是做笔记的时候忘记写来源了，做完笔记很久才写博客。专栏目录：记录自己的嵌入式学习之路-CSDN博客目录 1 基础——字符设备驱动 1.1 分配设备号（驱动入口使用）…...

编程日记 2025/7/3 1:24:16

BUUCTF——禁止套娃

BUUCTF——禁止套娃进入靶场一个近乎空白的页面看一下框架没什么有用的信息，扫个目录吧只扫出来给flag.php，但是0B，估计又是个空网站拼接访问一下果然又是什么都没有没有突破口 githack找找看看也没有源码吧 <?php include …...

编程日记 2025/6/29 5:22:25

Spring MVC @RequestBody 注解怎么用？接收什么格式的数据？

RequestBody 注解的作用 RequestBody 将方法上的参数绑定到 HTTP 请求的 Body（请求体）的内容上。当客户端发送一个包含数据的请求体（通常在 POST, PUT, PATCH 请求中）时，RequestBody 告诉 Spring MVC 读取这个请求体…...

编程日记 2025/7/14 19:18:51

线性DP(动态规划)

线性DP的概念（视频） 学习线性DP之前，请确保已经对递推有所了解。一、概念 1、动态规划不要去看网上的各种概念，什么无后效性，什么空间换时间，会越看越晕。从做题的角度去理解就好了，动态规划…...

编程日记 2025/6/29 5:13:29

Qt中实现工厂模式

在Qt中实现工厂模式可以通过多种方式，具体选择取决于需求和场景。以下是几种常见的实现方法： 1. 简单工厂模式通过一个工厂类根据参数创建不同对象。cppclass Shape {public: virtual void draw() 0; virtual ~Shape() default;};class Circle : publ…...

编程日记 2025/6/29 5:13:30

基于 Dify + vLLM插件 + Qwen3 构建问答机器人Docker版

前提条件硬件要求： 推荐 NVIDIA GPU (至少 16GB 显存，Qwen3 可能需要更多) 至少 32GB 内存足够的存储空间 (Qwen3 模型文件较大) 软件要求： Docker 和 Docker Compose Python 3.8 CUDA 和 cuDNN (与你的 GPU 兼容的版本) 安装步骤…...

编程日记 2025/6/29 6:17:46

【Linux】Linux应用开发小经验

基于Petalinux工具链的Linux应用开发小经验，未完待续... 部分图片和经验来源于网络，若有侵权麻烦联系我删除，主要是做笔记的时候忘记写来源了，做完笔记很久才写博客。专栏目录：记录自己的嵌入式学习之路-CSDN博客目录…...

编程日记 2025/6/29 8:16:13

第39课绘制原理图——绘制命令在哪里？

绘制原理图符号的命令在哪里？ 在新建完原理图之后，我们就可以在原理图上绘制各种相关的符号了。我们基本会从以下的两个地方，找到绘制各种符号的命令： 菜单栏中的“放置”菜单； 悬浮于设计窗口中的快速工具条在初…...

编程日记 2025/6/29 6:48:37

第十四篇：系统分析师第三遍——15章

目录一、目标二、计划三、完成情况四、意外之喜(最少2点)1.计划内的明确认知和思想的提升标志2.计划外的具体事情提升内容和标志五、总结六、后面准备怎么做？ 一、目标通过参加考试，训练学习能力，而非单纯以拿证为目的。 1.在复习过程中&…...

编程日记 2025/6/29 8:04:49

市面上所有大模型apikey获取指南(持续更新中)

阿里云(千问) 官方文档： 百炼控制台 1. 登录百炼控制台 2.前往我的api页面百炼控制台 3.创建api4. 添加描述（用于aichat） Deepseek 官方文档：首次调用 API | DeepSeek API Docs 1. 登录api平台 DeepSeek 开放平台 2. Deep…...

编程日记 2025/6/29 6:33:42

Java框架“若依RuoYi”前后端分离部署

运行环境 Eclipse IDE for Enterprise Java and Web Developers 下载Eclipse解压Eclipse到文件夹 Maven 下载Maven解压Maven到文件夹配置环境变量MAVEN_HOME为Maven安装位置配置环境变量path为%MAVEN_HOME%\bin Redis 下载Redis解压Redis到文件夹配置环境变量path为Redis安装位…...

编程日记 2025/6/29 6:36:48

计网_可靠传输ARQ机制

2024.09.04：网工老姜&beokayy网工学习笔记第5节可靠传输机制 5.1 可靠传输5.2 ARQ机制、ARQ协议5.3 ARQ简介（可靠传输）5.3.1 停止等待协议（1）无差错情况（2）有差错情况确认丢失确认迟到 5.…...

编程日记 2025/6/29 5:18:16

实验-组合电路设计1-全加器和加法器（数字逻辑）

目录一、实验内容二、实验步骤 2.1 全加器的设计 2.2 加法器的设计三、调试过程 3.1 全加器调试过程 2.加法器的调试过程四、实验使用环境五、实验小结和思考一、实验内容 a) 介绍在这次实验中，你将熟悉 Logisim 的操作流程，并且学习…...

编程日记 2025/7/2 18:31:19

软件管理（安装方式）

1.rpm安装 1.1.rpm介绍 rpm软件包名称: 软件名称版本号(主版本、次版本、修订号) 操作系统 -----90%的规律举例：openssh-6.6.1p1-31.el7.x86_64.rpm 数字是版本号：第一位主版本号，第二位次版本号，带横杠的是修订号， el几---操作系统的版本。 #用rpm安装需要考虑如下信…...

编程日记 2025/6/29 6:38:21

工作记录 2015-07-15

工作记录 2015-07-15 序号工作相关人员 1 在CDAEditor上增加签名的处理，已经基本改完。明天整理说明文档，更新193服务器。郝需要改了签名的处理增加了签名的按钮： 已经签名过的会有提示： 签名后PDF的预览如下&#xf…...

编程日记 2025/6/29 5:13:31

《算法导论(第4版)》阅读笔记：p4-p5

《算法导论(第4版)》学习第 3 天，p4-p5 总结，总计 2 页。一、技术总结 1.instance Thus, given the input sequence h31; 41; 59; 26; 41; 58i, a correct sorting algorithm returns as output the sequence h26; 31; 41; 41; 58; 59i. Such an inp…...

编程日记 2025/6/29 6:57:26

【Mytais系列】Update语句执行流程

以下是通过时序图和文字说明详细描述的 MyBatis 执行 UPDATE/INSERT/DELETE 语句的完整流程，包括缓存清理、事务提交和数据库操作的各个环节： 时序图（Sequence Diagram） 详细执行流程解析 1. 客户端发起更新请求客户端调用…...

编程日记 2025/6/29 7:17:25

LeetCode —— 145. 二叉树的后序遍历

😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️…...

编程日记 2025/6/29 8:12:54

Python函数参数机制深度解析与最佳实践

引言在Python开发中，函数的参数机制是构建灵活、可维护代码的核心要素。本文将通过7个关键维度深入剖析函数参数的底层原理与高级用法，结合代码实例揭示参数传递的本质规律，助您掌握工业级函数设计技巧（基于Python 3.12环境验证…...

编程日记 2025/6/29 8:06:04

ARM 算数指令

加法 ADD 减法 SUB 取负 NEG 比较 CMP 乘法 MUL 移位 LSL、LSR、ASL、ASR、ROL、ROR加法和减法绝大多数微处理器都实现了带进位的加法指令，能够将两个操作数和条件码寄存器中的进位位加到一起。这条指令会使字长大于计算机固有字长的链接运算更加方便。说明了如何…...

编程日记 2025/6/29 7:58:01

普通IT的股票交易成长史--20250502 突破（2）

声明：本文章的内容只是自己学习的总结，不构成投资建议。文中观点基本来自yt站方方土priceaction，综合自己的观点得出。感谢他们的无私分享。送给自己的话： 仓位就是生命，绝对不能满仓！！&#…...

编程日记 2025/6/29 5:13:32

什么是 Redis？

什么是 Redis？ Redis（全称是 Remote Dictionary Server，远程字典服务器）是一个非常快的开源内存数据库，它主要用来存储“键-值”对类型的数据。与传统的数据库不太一样，Redis的数据主要存放在内存中，所以它读写速度特别快。通俗比喻：想象你有一个小仓库，里面放了…...

编程日记 2025/7/4 12:39:46

IEEE LaTeX会议模板作者对齐、部门长名称换行

第二行作者对齐参考链接： https://tex.stackexchange.com/questions/458204/ieeetran-document-class-how-to-align-five-authors-properly/458208#458208https://tex.stackexchange.com/questions/582487/how-to-align-four-author-names-in-the-ieee-conferenc…...

编程日记 2025/6/29 5:27:09

前端面经-VUE3篇（二）--vue3组件知识（二）依赖注入、异步组件、生命周期、组合式函数、插件

目录一、依赖注入 1、依赖注入是什么？ 2、最基础的使用 3、为什么使用依赖注入？ 4、使用 Symbol 作注入名二、异步组件 1、什么是异步组件？ 2、最基础用法：defineAsyncComponent 3、在模板中使用异步组件 4、配置加载状态…...

编程日记 2025/6/29 8:14:33

Manus联合创始人：公司产品基于Claude和阿里千问大模型开发

3月11日消息，日前，Manus官方在社交平台转发了公司联合创始人、首席科学家季逸超对Manus的技术解读，季逸超在评论区回复网友关于“Manus使用了哪一个基础大模型”这一问题时回复称，“我们用过Claude，也用过不同版本的Qw…...

编程日记 2025/6/29 6:17:13

华为云Flexus+DeepSeek征文｜快速搭建Dify LLM应用开发平台教程

目录部署Dify-LLM应用开发平台开始使用一键卸载注意事项部署Dify-LLM应用开发平台 1、首先需要访问快速搭建Dify-LLM应用开发平台-华为云 2、使用"一键部署"功能快速搭建Dify平台快速搭建Dify LLM应用开发平台-云社区-华为云，本文在这里选择一键部署&…...

编程日记 2025/6/29 6:09:04

简介QML中的Canvas

2025年5月3日，周六晚上 QML中的Canvas是一个强大的绘图组件，允许开发者通过JavaScript在界面上进行动态的2D图形绘制。它类似于HTML5的<canvas>元素，适用于实现自定义图形、动画、游戏开发以及图表绘制等场景。核心特性绘图能力 • …...

编程日记 2025/6/29 7:25:21

装饰器@wraps(func)详解

1. wraps(func) 的核心作用 wraps 是 Python 标准库 functools 提供的装饰器，用于保留被装饰函数的原始元信息。它通过将原函数的 __name__、__doc__、__module__ 等属性复制到装饰器内部的包装函数中，避免装饰器对函数身份信息的“掩盖”。 2. 元信息…...

编程日记 2025/6/29 5:18:13

vue的diff算法是什么、比较方式，原理分析、示例解释讲解

Vue Diff算法概述 Vue 的 Diff 算法是一种高效的虚拟 DOM 更新机制，用于最小化真实 DOM 的操作开销。它通过比较新旧 Virtual DOM 树中的差异，仅更新那些实际发生改变的部分，从而提升性能。定义 Diff 算法的核心目标是在 MVVM 开发模式下…...

编程日记 2025/6/29 6:09:03

Day04 新增套餐

###今天的任务主要是自主完成套餐管理的模块### 1.新增套餐在前端页面接口中我们可以看到在新增套餐的时候需要选择添加到菜单中的菜品因此我们需要设计一个接口可以通过根据分类id（category_id）来查询该分类下的菜品 1.1根据分类id查询分类下的菜…...

编程日记 2025/6/29 8:14:49

WEB前端小练习——记事本

一、登陆页面 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>记事本登录注册</title><link…...

编程日记 2025/6/29 5:31:41

在多线程环境下如何设计共享数据结构保证原子操作与数据一致性

在多线程环境下如何设计共享数据结构保证原子操作与数据一致性 1. 引言在现代软件开发中，多线程编程是提升程序性能和响应速度的重要手段。然而，多线程环境下的共享数据管理极具挑战性，若处理不当，可能引发竞争条件（Race Conditions）、数据不一致（Data Inconsiste…...

编程日记 2025/6/29 7:28:01

洛谷 P1850 [NOIP 2016 提高组] 换教室

题目传送门前言终于自己想出概率期望 d p dp dp 的状态了，但是依旧没能相对转移方程。（招笑） 暴力这题部分分和特殊情况分给的挺多的，所以先拿部分分。一、思路先跑一边 F l o y d Floyd Floyd 最短路求出两点间最短距…...

编程日记 2025/6/29 7:27:08

1penl配置

好的，根据您提供的 1pctl 命令输出信息，我们来重新依次回答您的所有问题： 第一：1Panel 怎么设置 IP 地址？ 根据您提供的 user-info 输出： 面板地址: http://$LOCAL_IP:34523/93d8d2d705 这里的 $LOCAL_I…...

编程日记 2025/6/29 5:13:33

Windows下调试WebRTC源码

一、引言《Windows下编译WebRTC源码》讲述了Windows下编译WebRTC源码的方法。本文在其基础之上，讲述使用Visual Studio调试WebRTC源码的方法。二、生成Visual Studio工程文件按照《Windows下编译WebRTC源码》编译出webrtc.lib 后，执行下面的命令生…...

编程日记 2025/7/9 0:16:11

基于大模型的肾结石诊疗全流程风险预测与方案制定研究报告

目录一、引言 1.1 研究背景与意义 1.2 国内外研究现状 1.3 研究目标与内容二、大模型技术原理与应用概述 2.1 大模型的基本原理 2.2 大模型在医疗领域的应用进展 2.3 适用于肾结石预测的大模型选择与依据三、术前风险预测与准备 3.1 患者身体状况评估 3.2 结石情…...

编程日记 2025/6/29 5:27:21

《ATPL地面培训教材13：飞行原理》——第5章：升力

翻译：刘远贺；工具：Cursor & Claude 3.7；过程稿第5章：升力目录空气动力系数基本升力方程回顾升力曲线升力曲线的解释速度-动压关系密度高度翼型剖面升力特性阻力特性简介升阻比飞机重量对最小飞行速度的影响表…...

编程日记 2025/6/29 5:13:38

STM32部分：2、环境搭建

飞书文档https://x509p6c8to.feishu.cn/wiki/DQsBw76bCiWaO4kS8TXcWDs0nAh Keil MDK用于编写代码，编译代码芯片支持包，用于支持某类芯片编程支持STM32CubeMX用于自动生成工程，减少手动重复工作 STM32F1系列芯片支持包软件下载直接下载&am…...

编程日记 2025/6/28 20:04:41

最小生成树

题目描述

相关文章：