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

算法竞赛进阶指南.次小生成树

news 来源：原创 2025/8/12 8:31:10

题目

356. 次小生成树

算法标签: $Kr u s ka l$ , $MST$ , 倍增优化, $l c a$

思路

因为要求的是严格次小生成树, 假设最小生成树的和为 $s$ , 遍历每一个非树边 $e$ , 那么最后答案就是 $\min (s + e.w - v)$ , $v$ 是当前非树边的路径上最长的边
如果最长边是最小生成树的边, 使用次长边, 因此需要处理两个数组 $d 1$ , $d 2$ 分别代表最长边和次长边, 算法时间复杂度 $O(E\log E)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;
const int N = 1e5 + 10, M = 6e5 + 10, K = 18;
const int INF = 0x3f3f3f3f;int n, m;
struct Edge {int u, v, w;bool is_tr = false;bool operator< (const Edge &e) const {return w < e.w;}
} edges[M];
int head[N], ed[N << 1], ne[N << 1], w[N << 1], idx;
int fa[N][K], depth[N];
int d1[N][K], d2[N][K];
int p[N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}void add(int u, int v, int val) {ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}LL kruskal() {sort(edges, edges + m);for (int i = 0; i <= n; ++i) p[i] = i;LL res = 0;for (int i = 0; i < m; ++i) {auto &[u, v, w, is_tr] = edges[i];int fa1 = find(u), fa2 = find(v);if (fa1 == fa2) continue;res += w;p[fa2] = fa1;is_tr = true;add(u, v, w), add(v, u, w);}return res;
}void bfs() {int q[N], h = 0, t = -1;q[++t] = 1;memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;while (h <= t) {int u = q[h++];for (int i = head[u]; ~i; i = ne[i]) {int v = ed[i];if (depth[u] + 1 < depth[v]) {depth[v] = depth[u] + 1;q[++t] = v;fa[v][0] = u;d1[v][0] = w[i];d2[v][0] = -INF;for (int k = 1; k < K; ++k) {int mid = fa[v][k - 1];fa[v][k] = fa[mid][k - 1];int arr[4] = {d1[v][k - 1],d2[v][k - 1],d1[mid][k - 1],d2[mid][k - 1]};int val1 = -INF, val2 = -INF;for (int j = 0; j < 4; ++j) {if (arr[j] > val1) val2 = val1, val1 = arr[j];else if (arr[j] > val2 && arr[j] < val1) val2 = arr[j];}d1[v][k] = val1;d2[v][k] = val2;}}}}
}int lca(int u, int v, int val) {if (depth[u] < depth[v]) swap(u, v);vector<int> vec;for (int k = K - 1; k >= 0; --k) {if (depth[fa[u][k]] >= depth[v]) {vec.push_back(d1[u][k]);vec.push_back(d2[u][k]);u = fa[u][k];}}if (u != v) {for (int k = K - 1; k >= 0; --k) {if (fa[u][k] != fa[v][k]) {vec.push_back(d1[u][k]);vec.push_back(d2[u][k]);vec.push_back(d1[v][k]);vec.push_back(d2[v][k]);u = fa[u][k], v = fa[v][k];}}vec.push_back(d1[u][0]);vec.push_back(d2[u][0]);vec.push_back(d1[v][0]);vec.push_back(d2[v][0]);}int val1 = -INF, val2 = -INF;for (int t : vec) {if (t > val1) val2 = val1, val1 = t;else if (t > val2) val2 = t;}if (val1 < val) return val1;if (val1 == val) return val2;return -INF;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;edges[i] = {u, v, w};}LL sum = kruskal();bfs();LL ans = 1e18;for (int i = 0; i < m; ++i) {auto &[u, v, w, is_tr] = edges[i];if (is_tr) continue;ans = min(ans, sum + w - lca(u, v, w));}cout << ans << "\n";return 0;
}

*警示后人

因为求的是严格次小生成树, 因此在计算的时候不是arr[j] > val2而是arr[j] > val2 && arr[j] < val1, 否则求出的就不是严格的了

算法竞赛进阶指南.次小生成树

目录题目算法标签: K r u s k a l Kruskal Kruskal, M S T MST MST, 倍增优化, l c a lca lca思路代码*警示后人题目 356. 次小生成树算法标签: K r u s k a l Kruskal Kruskal, M S T MST MST, 倍增优化, l c a lca lca 思路因为要求的是严格次小生成树, 假设最…...

编程日记 2025/8/12 8:31:10

ElasticSearch基本概念

为什么要使用ElasticSearch Elasticsearch 主要为系统提供搜索功能， MySQL 这类传统关系型数据库主要为系统提供数据存储功能 Elasticsearch 的优势 ： 支持多种数据类型，非结构化，数值，地理信息。简单的 RESTful AP…...

编程日记 2025/8/11 16:01:55

普通IT的股票交易成长史--20250508晚复盘

声明：本文章的内容只是自己学习的总结，不构成投资建议。价格行为理论学习可参考简介中的几位，感谢他们的无私奉献。送给自己的话： 仓位就是生命，绝对不能满仓！！！！&…...

编程日记 2025/6/29 4:58:51

SAP 交货单行项目含税金额计算报cx_sy_zerodivide处理

业务背景：SAP交货单只有数量，没有金额，所以开发报表从订单的价格按数量计算交货单的金额。用户反馈近期报表出现异常： ****2012/12/12 清风雅雨规格变更 Chg 修改开始 ** 修改原因:由于余数为0时，可能会报错溢出。…...

编程日记 2025/6/29 2:33:21

基于译码器和锁存器的运行逻辑的简易算法

74HC138 def decoder_74hc138(E1, E2, E3, A0, A1, A2):output [1] * 8 # 默认全高电平# 检查使能条件：E1和E2低电平，E3高电平if E1 0 and E2 0 and E3 1:# 计算地址索引（A2为高位，A0为低位）index (A2 <<…...

编程日记 2025/8/8 7:33:10

用电信息采集中的天线种类

一、4G/3G/2G 频率范围“698-960/1710-2700MHz 输入阻抗：50Ω 电压驻波比：<3.0 增益：5dBi/7dBi/9dBi； 824MHz～960MHz频段本体增益≥3.0dBi 1710MHz～2700MHz频段本体增益≥5.0dBi 天线长度225*30mm…...

编程日记 2025/8/12 8:31:10

2025年4月AI算力领域热点事件全景报告

目录一、政策要闻 01欧洲央行召开会议讨论AI影响 02中国生成式AI备案制落地 03多国政府公布AI基础设施投资计划 04香港发布生成式AI技术及应用指引 05美国出口管制政策影响 06欧盟《人工智能法案》落地 07中国 “东数西算” 工程深化 08美国CHIPS法案争议 09中国发…...

编程日记 2025/8/12 8:26:01

数据结构-非线性结构-二叉树

概述 /** * 术语 * 根节点（root node）：位于二叉树顶层的节点，没有父节点。 * 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。 * 边（edge）&…...

编程日记 2025/8/11 20:59:15

Android开发补充内容

Android开发补充内容 fragment通信生命周期 Okhttp基本使用websocket Retrofit基本使用 RxJava基本使用定时任务 Hilt基本使用进阶使用例子组件库Material ComponentsJetpack Compose fragment 通信 fragment于activity通信的一种原生方法是使用Bundle： Bundle …...

编程日记 2025/8/12 8:28:26

Go主要里程碑版本及其新增特性

Go 语言自 2009 年诞生以来，经历了多个里程碑版本的迭代，每个版本都引入了重要特性和改进。以下是 Go 语言的主要版本及其关键特性： Go 1.0 (2012-03-28) 首个稳定版，承诺向后兼容（Go 1 兼容性保证）。核心…...

编程日记 2025/6/29 3:55:47

To cut a snippet from a video based on timestamps like 02:52 to 04:20, the best tool is FFmpeg, which is fast, free, and doesn’t re-encode the video (so it keeps original quality if you don’t want re-encoding). Here’s the command you can run in a termi…...

编程日记 2025/8/8 17:27:06

无刷电机控制算法策略

目录一、基础控制算法二、高性能算法三、无感算法四、智能算法五、特殊场景算法无刷电机的核心控制算法主要包括以下类型： 一、基础控制算法六步换向法（梯形控制） 通过霍尔传感器检测转子位置，按固定顺序切换…...

编程日记 2025/8/12 8:31:09

LeetCode算法题(Go语言实现)_61

题目你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金…...

编程日记 2025/7/11 4:40:59

Kafka消息不丢失处理

kafka作为消息中间件，吞吐量大（至于为啥吞吐量大，本文不做介绍），所以大家用的多。涉及到异构数据库更换，以及数据预处理后的迁移，基本想到的都是通过kafka。概览图我先画个图生产者到kafka…...

编程日记 2025/6/29 2:14:13

Python+ffmpeg 实现给视频添加字幕

创作灵感孩子学校经常留作业，需要提交一段录制的视频，视频上要求添加学校、班级、姓名等信息的字幕，手机自带的相机软件字幕添加位置要么只能添加在视频正中，要么无法添加多行文本，要么只能添加在片头或者片尾&#…...

编程日记 2025/8/12 8:28:26

QMK键盘固件自定义指南 - 打造你的专属键盘体验

QMK键盘固件自定义指南 - 打造你的专属键盘体验 🚀 前言在机械键盘的世界里，QMK固件让你的键盘不再只是简单的输入设备，而是可以按照你的意愿定制的强大工具。本文将深入浅出地介绍如何自定义QMK键盘的行为，从基础概念到高级应…...

编程日记 2025/8/11 23:37:02

Linux-openeuler更换yum镜像源

将 openEuler 系统镜像源更换为华为镜像以openEuler 24.03 LTS SP1 为例。操作前建议备份原配置文件，并确保系统已联网。一、确认系统版本与架构查看系统版本： [rooteulerzy yum.repos.d]# cat /etc/os-releaseNAME"openEuler"VERSION&qu…...

编程日记 2025/7/30 22:39:59

手势、鼠标滑动实现界面切换

手势： #include <QApplication> #include "mainwindow.h"int main(int argc, char *argv[]) {QApplication app(argc, argv);MainWindow window;window.show();return app.exec(); }#ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainW…...

编程日记 2025/8/11 18:18:55

什么是变量提升？（形象的比喻）

当然！可以用几个生活中的比喻来形象地解释变量提升： 1. 书架的占位符想象你有一个书架，但还没放书。 • 变量提升（var）： 你先在书架上贴了一个标签（比如写“我的书”）&…...

编程日记 2025/8/12 4:20:25

趣味编程：答案之书

概述：该篇博客主要介绍的是曾经一度风靡全网的答案之书小程序。目录 1. 效果展示 2. 源码展示 3. 代码逻辑详解 3.1 头文件与全局变量 3.2 main函数 3.3 主循环 3. 4 绘制界面 4. 运行问题 5.小结 1. 效果展示该小程序是动态的效果， 因此实…...

编程日记 2025/7/4 12:27:25

用kompose将docker-compose文件转换为K8S资源清单

一、什么是kompose Kompose 是什么？它是一个转换工具，可将 Compose （即 Docker Compose）所组装的所有内容转换成容器编排器（Kubernetes 或 OpenShift）可识别的形式。更多信息请参考 Kompose 官网 Kompos…...

编程日记 2025/7/1 5:23:54

Linux中的防火墙

概述防火墙通过一系列规则来过滤网络数据包，决定哪些数据包可以进入或离开系统，哪些数据包将被阻止，以此来保护系统免受未经授权的访问、恶意攻击和潜在的安全威胁。常见的防火墙软件 iptables：是 Linux 系统中常用的防火墙工…...

编程日记 2025/8/12 8:31:10

AI开发跃迁指南（第三章：第四维度1——Milvus、weaviate、redis等向量数据库介绍及对比选型）

1.向量数据库简介向量数据库（Vector Database）是专门为存储和查询高维向量数据而设计的数据库，主要用于处理由机器学习模型生成的嵌入向量（Embeddings）。它在人工智能（AI）、自然语言处理&…...

编程日记 2025/6/29 3:49:21

深度学习笔记41_调用Gensim库训练Word2Vec模型

🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者：K同学啊 | 接辅导、项目定制一、我的环境 1.语言环境：Python 3.8 2.编译器：Pycharm 3.深度学习环境： torch1.12.1cu113torchvision…...

编程日记 2025/6/29 3:58:58

Windows Server 2025 安装AMD显卡驱动

运行显卡驱动安装程序，会提示出问题。但是此时资源已经解压来到驱动路径 C:\AMD\AMD-Software-Installer\Packages\Drivers\Display\WT6A_INF 打开配置文件，把这两行替换掉 %ATI% ATI.Mfg, NTamd64.10.0...16299, NTamd64.10.0, NTamd64.6.0, NTamd64.…...

编程日记 2025/7/11 9:12:05

debian安装docker

debian安装docker <在Debian上安装Docker的步骤》在Debian上安装Docker通常涉及几个步骤，以确保你能够顺利运行Docker容器。下面是一份详细的指南，帮助你在Debian系统上安装Docker。 1. 更新你的包列表首先，更新你的包列表以确保所有…...

编程日记 2025/6/29 3:21:28

uniapp上架苹果APP Store踩雷和部分流程注意事项（非完整流程）

本文是uniapp打包成ios上架到苹果商店一系列踩雷和部分流程介绍 1.打包需要俩个证书需要xx..mobileprovision和xx.p12证书并且ios打包一天最多5次，超出需要2元/1次付费打包，证书需要使用苹果电脑生成，以下为证书生成教程iOS证书(.p12)和描述…...

编程日记 2025/8/7 15:37:37

【吃透 Elasticsearch 的核心原理】学习步骤

要真正，需深入以下关键机制（结合最新技术演进）： 一、倒排索引机制核心三要素 Term Index：FST 结构加速前缀匹配（如 ap* 查询）Term Dictionary：存储所有 token 及统计信息&#xff…...

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

springboot使用mybatisPlus进行数据库增删改查

springboot使用mybatisPlus进行数据库增删改查提示：帮帮志会陆续更新非常多的IT技术知识，希望分享的内容对您有用。本章分享的是springboot的使用。前后每一小节的内容是存在的有：学习and理解的关联性。【帮帮志系列文章】：每个…...

编程日记 2025/8/9 22:28:14

移动端前端开发中常用的css

在开发移动端项目的时候，很多样式都是相同的，比如说图标大小，头像大小，页面底部保存(添加按钮），项目主体颜色等等，对于这些在项目中常用到的，通常都会写在公共样式中（pub…...

编程日记 2025/7/20 3:33:23

C/C++内存分布

内存分布示意图： 内存分布各区域详解： 内核空间： 放置操作系统相关的代码和数据。（用户不能直接进行操作 ------ 可以通过调用系统提供的 api 函数） 栈区： 又叫堆栈，非静态局部变量/函数参数/…...

编程日记 2025/8/10 10:24:59

Sass @import rules are deprecated and will be removed in Dart Sass 3.0.0.

版本：原因在 Dart Sass 3.0.0 中， @import 规则将被弃用，推荐使用 @use 和 @forward 规则来替代。 1.@use替代@import @use 规则允许你引入其他 Sass 文件中的变量、混合器和函数，并且可以避免命名冲突。示例： style.scss @use variables;body {color: variables.$pr…...

编程日记 2025/8/10 19:02:49

【计算机网络】用户从输入网址到网页显示，期间发生了什么？

1.URL解析浏览器分解URL：https://www.example.com/page 协议：https域名：www.example.com路径：/page 2.DNS查询： 浏览器向DNS服务器发送查询请求，将域名解析为对应的IP地址。 3.CDN检查(如果有)&#…...

编程日记 2025/7/7 15:03:22

使用adb设置wifi相关

其他的可以参考以下指令 Android 使用adb操作WiFi连接扫描等相关指令_adb wifi-CSDN博客但是如果你的wifi账号出现中文的时候： 例如：ssid "wolf的网络" 这种类型的时候，直接使用adb指令是有问题的，基本都会出现乱码…...

编程日记 2025/6/29 3:12:25

MySQL数据库创建、删除、修改

一：建库建表我们以学校体系进行建表。将数据库命名为school。以下代码中的大写均可小写不影响。如CREATE DATABASE与create database相同四个关键的实体分别是学院、老师、学生和课程，其中，学生跟学院是从属关系，这个关系从…...

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

【Android】动画原理解析

一，基础动画基础动画，有四种，分别是平移（Translate）、缩放（Scale）、Rorate（旋转）、Alpha（透明度），对应Android中以下四种。 1，Animation基类 1，基本概念 1，插值器插值器的作用，是控制动画过程的参数，可以理解为时间（t）与动画进程（d）的函数，动画仅…...

编程日记 2025/6/29 4:07:18

C++从入门到实战（十四）初识STL与STL简介

C从入门到实战（十四）初识STL与STL简介前言一、什么是 STL？二、STL 的版本三、STL六大组件（目前了解即可，后面会逐步讲解）1. 容器（Containers）—— 装数据的“盒子”2. 算法&#xf…...

编程日记 2025/8/6 22:27:20

力扣-142.环形链表II

题目描述给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。不允许修改链表。 class Solution { public:ListNode *detectCycle(ListNode *head) {ListNode *fast head;ListNode *slow head;while (fast) {…...

编程日记 2025/8/7 10:58:02

ERC-20与ERC-721：区块链代币标准的双星解析

一、代币标准的诞生背景在以太坊生态中，代币标准是构建去中心化应用（DApps）的基石。ERC-20与ERC-721分别代表同质化与非同质化代币的两大核心标准，前者支撑着90%以上的加密资产流通，后者则开启了数字资产唯一性的新时…...

编程日记 2025/7/13 23:31:44

图像管理与人脸识别工具深度解析

这篇Python应用程序代码实现了一个功能丰富的图像管理和人脸识别工具，它集成了多种实用功能，包括人脸检测与裁剪、屏幕截图以及生成PDF等核心功能。我将深入分析这个应用程序的架构、功能和实现方式，帮助读者理解其设计思路和关键技术点。 C…...

编程日记 2025/6/29 2:14:14

【图片合并PDF】一次性将多个文件夹里的图片批量按文件夹为单位合并PDF，多个文件夹图片合并PDF，基于WPF的实现方案

设计行业：设计师需要将项目设计稿按文件夹整理并合并为PDF交付客户摄影行业：摄影师按主题分类的照片需要合并为PDF存档或分享企业文档管理：市场调研部门需要将分散在不同文件夹的调研图片合并为PDF报告教育领域：教师需要将学生的作业图片按班…...

编程日记 2025/6/29 2:24:36

Matlab 数控车床进给系统的建模与仿真

1、内容简介 Matlab217-数控车床进给系统的建模与仿真可以交流、咨询、答疑 2、内容说明略摘要:为提高数控车床的加工精度,对数控车床进给系统中影响加工精度的主要因素进行了仿真分析研动系统的数学模型,利用MATLAB软件中的动态仿真工具究:依据机械动力学原理建立了…...

编程日记 2025/8/10 3:45:55

HOW - 在 Mac 上的 Chrome 浏览器中调试 Windows 场景下的前端页面

文章目录为什么需要模拟 Windows 环境？一、修改 User-Agent 模拟 Windows 浏览器方法 1：通过 Chrome 开发者工具修改 UA方法 2：使用浏览器插件二、模拟 Windows 的字体和滚动条样式1. 模拟 Windows 字体2. 强制显示滚动条（模拟 …...

编程日记 2025/8/9 15:25:02

微信小程序执行C语言库的详细方案

以下是微信小程序中执行C语言库的详细技术方案，分为环境准备、开发流程、优化技巧三个部分： 一、环境准备阶段 1. 工具链安装 # 安装Emscripten核心工具链 git clone https://github.com/emscripten-core/emsdk.git cd emsdk ./emsdk install latest .…...

编程日记 2025/8/11 4:07:45

如何用分布式防御抵扣大规模DDoS攻击？

DDoS攻击是当前最严峻的网络安全威胁之一，其通过海量请求耗尽目标资源，导致服务瘫痪。面对攻击规模的指数级增长，传统的单点防御已难以应对。本文将结合最新技术趋势，探讨分布式防御体系在抵御大规模DDoS攻击中的核心策略与实践。…...

编程日记 2025/8/11 18:45:46

【MySQL】存储引擎 - MyISAM详解

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/8/2 5:00:31

如何在Jmeter中调用C程序？

在JMeter中调用C语言程序可以通过以下几种方式实现： 方法一：使用OS Process Sampler JMeter的“OS Process Sampler”可以用来调用外部程序，包括C语言编写的可执行文件。步骤： 准备C语言程序： 编写C语言代码并编译…...

编程日记 2025/8/11 11:36:13

PyTorch 版本、torchvision 版本和 Python 版本的对应关系

PyTorch 版本、torchvision 版本和 Python 版本的对应关系在深度学习领域，PyTorch 及其配套库 torchvision 的使用极为广泛。但不同版本的 PyTorch、torchvision 与 Python 之间存在严格的对应关系，若版本搭配不当，会导致代码运行出错…...

编程日记 2025/8/7 15:16:24

构建高可维护、易测试的异步任务系统：基于 Celery + Redis + Eventlet 的模块化架构实践

引言：为什么我们需要一个结构清晰的异步任务系统？ 在现代软件开发中，异步任务已经成为提升响应性能、解耦业务逻辑、支持高并发的重要手段。尤其对于测试工程师而言，异步任务往往意味着： 任务执行不可控状态追踪困难…...

编程日记 2025/8/10 20:34:52

《智能网联汽车自动驾驶功能场地试验方法及要求》 GB/T 41798-2022——解读

目录 1. 适用范围与核心目标 2. 试验核心要求 2.1 试验场地与环境 2.2 试验设备与数据采集 2.3 试验车辆要求 3. 试验过程与通过条件 4. 关键试验场景与方法 4.1 交通信号识别及响应 4.2 基础设施与障碍物识别 4.3 行人及非机动车场景 4.4 紧急避险与风险策略 5. 特…...

编程日记 2025/8/10 4:40:13

目录

题目

算法标签: K r u s k a l Kruskal Kruskal, M S T MST MST, 倍增优化, l c a lca lca

思路

代码

*警示后人

相关文章：

算法标签: $Kr u s ka l$ , $MST$ , 倍增优化, $l c a$