Kruscal建树+倍增LCA,蓝桥2023省赛,网络稳定性

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解


一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

2.网络稳定性 - 蓝桥云课 (lanqiao.cn)


二、解题报告

1、思路分析

考虑到如果给一棵树,查询任意两点间路径上最小边权,可以用倍增法+LCA来解决

但是给了一个图,又考虑到题目要求的是所有路径种最大的最小边权

那么对于两点间路径我们只需要保留最大的那一条即可

所以我们可以用Kruscal求最大生成树

然后套倍增法求LCA的板子即可

2、复杂度

时间复杂度: O((q+ n)logn + mlogm)空间复杂度:O(nlogn + m)

3、代码详解

#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <vector>
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
typedef pair<int,int> pii;
struct edge{int u, v, w;bool operator <(const edge& e)const{return w > e.w;}
}edges[M];
vector<pii> g[N];
int n, m, q, p[N], dep[N]{0}, f[N][20]{0}, cost[N][20]{0};
bitset<N> vis;
int findp(int x){return p[x] < 0 ? x : p[x] = findp(p[x]);
}
void merge(int x, int y){int px = findp(x), py = findp(y);if(px == py) return;if(p[px] > p[py]) swap(px, py);p[px] += p[py], p[py] = px;
}
void Kruscal(){sort(edges, edges + m);for(int i = 0, a, b, c; i < m; i++){a = edges[i].u, b = edges[i].v, c = edges[i].w;if(findp(a) == findp(b)) continue;merge(a, b);g[a].emplace_back(b, c), g[b].emplace_back(a, c);}
}
void dfs(int x, int fa){vis[x] = 1, dep[x] = dep[fa] + 1, f[x][0] = fa;for(int i = 1; i < 20; i++)f[x][i] = f[f[x][i-1]][i-1], cost[x][i] = min(cost[x][i - 1], cost[f[x][i-1]][i-1]);for(auto& [y, w] : g[x])if(y != fa)cost[y][0] = w, dfs(y, x);
}
int lca(int x, int y){if(dep[x] < dep[y]) swap(x, y);int ret = cost[x][0];for(int i = 19; i >= 0; i--)if(dep[f[x][i]] >= dep[y]) ret = min(ret, cost[x][i]), x = f[x][i];if(x == y) return ret;for(int i = 19; i >= 0; i--)if(f[x][i] != f[y][i]) ret = min(ret, min(cost[x][i], cost[y][i])), x = f[x][i], y = f[y][i];ret = min(ret, min(cost[x][0], cost[y][0]));return ret;
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);memset(p, -1, sizeof p);cin >> n >> m >> q;for(int i = 0, a, b, c; i < m; i++) cin >> a >> b >> c, edges[i] = {a, b, c};Kruscal();for(int i = 1; i <= n; i++)if(!vis[i]) dfs(i, 0);for(int i = 0, a, b; i < q; i++){cin >> a >> b;if(findp(a) != findp(b)) cout << "-1\n";else cout << lca(a, b) << '\n';}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/271675.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

自动驾驶预测与决策规划(nuplan数据集)

欢迎大家关注我的B站&#xff1a; 偷吃薯片的Zheng同学的个人空间-偷吃薯片的Zheng同学个人主页-哔哩哔哩视频 (bilibili.com) 目录 1.概述 2 数据采集 3.开环与闭环仿真 4.数据注释 5.场景 6.规划框架 6.1Train 6.2Simulation 6.3Metric 6.4Visualization 7.下载…

【2024.03.05】定时执行专家 V7.1 发布 - TimingExecutor V7.1 Release

目录 ▉ 软件介绍 ▉ 新版本 V7.1 下载地址 ▉ V7.1 新功能 ▼2024-03-03 V7.1 - 更新日志 ▉ V7.0 新UI设计 ▉ 软件介绍 《定时执行专家》是一款制作精良、功能强大、毫秒精度、专业级的定时任务执行软件。软件具有 25 种【任务类型】、12 种【触发器】触发方式&#x…

基于51单片机风速仪风速测量台风预警数码管显示

基于51单片机风速仪风速测量报警数码管显示 1. 主要功能&#xff1a;2. 讲解视频&#xff1a;3. 仿真4. 程序代码5. 设计报告&#x1f517;6. 下载链接资料下载链接&#xff1a; 基于51单片机风速仪风速测量报警数码管显示( proteus仿真程序设计报告讲解视频&#xff09; 仿真图…

CRMCHAT修复获取客户ip信息,地区信息

CRMCHAT修复获取客户ip信息&#xff0c;地区信息-TP源码网原因&#xff1a; 因pv.sohu.com/cityjson?ieutf-8接口已无法正确获取ip信息&#xff0c;导致后台站点统计无法正确获取用户ip信息&#xff0c;无法获取地区信息 修改 注释掉无用接口地址 修复ip信息 也可以使用&…

【Lazy ORM】 小工具 acw 本地客户端 你负责点击页面,他负责输出代码

介绍 wu-smart-acw-client 简称acw-client&#xff0c;是一个基于Lazy ORM定制的客户端代码生成小工具 Lazy ORM 小工具 acw 本地客户端 你负责点击页面&#xff0c;他负责输出代码安装 <dependency><groupId>top.wu2020</groupId><artifactId>wu-sma…

即插即用篇 | YOLOv8 引入 ParNetAttention 注意力机制 | 《NON-DEEP NETWORKS》

论文名称:《NON-DEEP NETWORKS》 论文地址:https://arxiv.org/pdf/2110.07641.pdf 代码地址:https://github.com/imankgoyal/NonDeepNetworks 文章目录 1 原理2 源代码3 添加方式4 模型 yaml 文件template-backbone.yamltemplate-small.yamltemplate-large.yaml

2024蓝桥杯每日一题(前缀和)

一、第一题&#xff1a;壁画 解题思路&#xff1a;前缀和贪心枚举 仔细思考可以发现B值最大的情况是一段连续的长度为n/2上取整的序列的累加和 【Python程序代码】 import math T int(input()) for _ in range(1,1T):n int(input())s input()l math.ceil(len(s)/…

图文并茂的讲清楚Linux零拷贝技术

今天我们来聊一聊Linux零拷贝技术&#xff0c;今天我们以一个比较有代表性的技术sendfile系统调用为切入点&#xff0c;详细介绍一下零拷贝技术的原理。 1.零拷贝技术简介 Linux零拷贝技术是一种优化数据传输的技术&#xff0c;它可以减少数据在内核态和用户态之间的拷贝次数&…

Linux报错排查-刚安装好的ubuntu系统无法ssh连接

Linux运维工具-ywtool 目录 一.问题描述二.问题解决2.1 先给ubuntu系统配置阿里云源2.2 安装openssh-server软件2.3 在尝试ssh连接,可以连接成功了 三.其他命令 一.问题描述 系统:ubuntu-18.04-desktop-amd64 系统安装完后,想要通过xshell软件连接系统,发现能Ping通系统的IP,但…

【探索Linux】—— 强大的命令行工具 P.26(网络编程套接字基本概念—— socket编程接口 | socket编程接口相关函数详细介绍 )

阅读导航 引言一、socket 常见API表二、函数详细介绍01. socket()02. bind()03. listen()04. accept()05. connect()06. send()07. recv()08. close()09. select()10. getaddrinfo()11. sendto()12. recvfrom()13. setsockopt()14. getsockopt()15. shutdown()16. inet_pton()1…

昇腾芯片解析:华为自主研发的人工智能处理器全面分析

在当今科技发展的浪潮中&#xff0c;昇腾芯片作为一种新兴的处理器&#xff0c;正引起广泛的关注和讨论。升腾芯片究竟是由哪家公司生产的&#xff1f;这个问题一直困扰着许多人。下面小编将全面介绍、分析升腾芯片的生产商及各类参数、应用&#xff0c;以便读者对其有更全面的…

centos7 python3.12.1 报错 No module named _ssl

https://blog.csdn.net/Amio_/article/details/126716818 安装python cd /usr/local/src wget https://www.python.org/ftp/python/3.12.1/Python-3.12.1.tgz tar -zxvf Python-3.12.1.tgz cd Python-3.12.1/ ./configure -C --enable-shared --with-openssl/usr/local/opens…

C++:Stack和Queue的模拟实现

创作不易&#xff0c;感谢三连&#xff01; 一、容器适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)&#xff0c;该种模式是将一个类的接口转换成客户希望的另外一个接口。 就如同是电源适配器将不适用的交流电…

css实现背景渐变叠加

线性渐变效果图: .box{width: 100vw;height: 100vh;background:linear-gradient(to bottom,transparent,#fff 30%),linear-gradient(to right,pink,skyblue);}径像渐变效果图&#xff1a; .box{width: 100vw;height: 100vh;background:linear-gradient(to bottom,transparent,#…

【JavaEE初阶】 JVM类加载简介

文章目录 &#x1f343;前言&#x1f332;类加载过程&#x1f6a9;加载&#x1f6a9;验证&#x1f6a9;准备&#x1f6a9;解析&#x1f6a9;初始化 &#x1f384;双亲委派模型&#x1f6a9;什么是双亲委派模型&#xff1f;&#x1f6a9;双亲委派模型的优点 ⭕总结 &#x1f343…

Vue.js 实用技巧:深入理解 Vue.mixin

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

开发一套小程序所需的费用取决于多个因素

随着移动互联网的发展&#xff0c;小程序已经成为许多企业和个人推广业务和服务的重要工具。 不过&#xff0c;对于很多想要开发小程序的人来说&#xff0c;最大的疑问就是开发一套小程序要花多少钱。 这个问题的答案并不是固定的&#xff0c;因为开发一个小程序的成本取决于几…

业务代码中如何使用装饰器模式?

装饰器模式&#xff08;Decorator Pattern&#xff09;介绍 装饰器模式&#xff08;Decorator Pattern&#xff09;是一种结构型设计模式&#xff0c;我们可以动态地给一个对象添加额外的职责。而不是通过继承增加子类的方式来扩展对象的功能&#xff0c;装饰器模式使用组合的…

Java注解介绍

Java注解 注解介绍元注解RetentionTargetDocumentedInherited接口类测试结果 注解介绍 Java注解&#xff08;Annotation&#xff09;是一种元数据&#xff08;Metadata&#xff09;的形式&#xff0c;它可以被添加到Java代码中的类、方法、变量、参数等元素上&#xff0c;以提…

AI时代PPT如何制作?用这10款pptai生成器一键制作!

ppt如何制作&#xff1f; 这可能是很多职场人或大学生日常头疼的问题&#xff0c;职场上随便一个工作汇报、提案展示、团队会议&#xff0c;学校里的小组作业、论文答辩等场景&#xff0c;都会用到ppt。 都说人是视觉动物&#xff0c;在两份文档内容质量一致的情况下&#xf…