P9235 [蓝桥杯 2023 省 A] 网络稳定性

*原题链接*

最小瓶颈生成树题,和货车运输完全一样。

先简化题意,q 次询问,每次给出 x,y,问 x 到 y 的所有路径集合中,最小边权的最大值。

对于这种题可以用kruskal生成树来做,也可以用倍增来写,但不管怎样都要先求出最大生成树,因为最小边权的最大值肯定会在最大生成树中出现。然后我们要做的就是在树中,求 x 到 y 的最短路径上的最小边权。这个可以倍增求,求解的过程类似求 lca。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=3e5+10,INF=0x3f3f3f3f;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,q,head[N],tot,f[N],fa[N][20],dep[N],fm[N][20];
struct node{int from,to,nxt,w;
}e[M*2],edge[M*2];
void add(int x,int y,int w){edge[++tot].to=y;edge[tot].w=w;edge[tot].nxt=head[x];head[x]=tot;
}
bool cmp(node a,node b){return a.w>b.w;
}int find(int x){if(x!=f[x]) f[x]=find(f[x]);return f[x];
}void kruskal(){for(int i=1;i<=n;i++) f[i]=i;sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++){int x=find(e[i].from),y=find(e[i].to);if(x==y) continue;f[x]=y,add(e[i].from,e[i].to,e[i].w),add(e[i].to,e[i].from,e[i].w);}
}void dfs(int x,int father){dep[x]=dep[father]+1,fa[x][0]=father;for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(y==father) continue;fm[y][0]=edge[i].w;dfs(y,x);}
}void init(){for(int i=1;(1<<i)<=n;i++){for(int j=1;j<=n;j++){fa[j][i]=fa[fa[j][i-1]][i-1];fm[j][i]=min(fm[j][i-1],fm[fa[j][i-1]][i-1]);}}
}int lca(int x,int y){if(dep[x]>dep[y]) swap(x,y);int k=log2(dep[y]+1),ans=INF;for(int i=k;i>=0;i--){if(dep[y]-(1<<i)>=dep[x]) ans=min(ans,fm[y][i]),y=fa[y][i];}if(x==y) return ans;for(int i=k;i>=0;i--){if(fa[x][i]!=fa[y][i]){ans=min(ans,min(fm[x][i],fm[y][i]));x=fa[x][i],y=fa[y][i];}}return min(ans,min(fm[x][0],fm[y][0]));
}int main(){n=read(),m=read(),q=read();for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();e[i]={x,y,0,w};}kruskal(),memset(fm,0x3f,sizeof(fm)),dfs(1,0),init();while(q--){int x=read(),y=read();if(find(x)!=find(y)) cout<<-1<<endl;else cout<<lca(x,y)<<endl;}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

程序员工作中经常使用的C/C++开源库

Bundle 项目地址&#xff1a;GitHub - r-lyeh-archived/bundle: :package: Bundle, an embeddable compression library: DEFLATE, LZMA, LZIP, BZIP2, ZPAQ, LZ4, ZSTD, BROTLI, BSC, CSC, BCM, MCM, ZMOLLY, ZLING, TANGELO, SHRINKER, CRUSH, LZJB and SHOCO streams in a …

Datawhale X 南瓜书 task02学习笔记

算法原理引入 样本点通常应该在模型的2侧&#xff0c;原因&#xff1a;在实际中&#xff0c;因为某种不可控的因素&#xff0c;测出来的样本点肯定是有误差的。如果样本数据点都在模型上&#xff0c;则说明在建立模型时&#xff0c;把误差也考虑进去了&#xff0c;这就是我们说…

9月21日 电子产品世界上海站沙龙

9月21日 电子产品世界上海站沙龙 有幸参加了 9月21日 14: 00 在上海 九江路 700号 上海南新雅皇冠假日酒店 4楼 举行的 TI MSPM0 MCU开发经验交流 会 本次邀请资深开发者&#xff0c;现场跟大家进行TI MSPM0 MCU开发经验交流&#xff0c;并详细展示基于TI MSPM0 MCU开发的实用…

动态规划day39|198. 打家劫舍、213. 打家劫舍 II(环形怎么处理?)、337. 打家劫舍 III(二叉树与动态规划的完美结合!)

动态规划day39|198. 打家劫舍、213. 打家劫舍 II&#xff08;环形怎么处理&#xff1f;&#xff09;、337. 打家劫舍 III&#xff08;二叉树与动态规划的完美结合&#xff01;&#xff09; 198. 打家劫舍213. 打家劫舍 II337. 打家劫舍 III 198. 打家劫舍 你是一个专业的小偷&…

盘点3款.NetCore(C#)开源免费商城系统

CoreShop商城 介绍 核心商城系统&#xff08;CoreShop&#xff09; 是基于 Asp.Net 8.0、Uni-App开发、支持可视化布局的小程序商城系统&#xff1b;前后端分离&#xff0c;支持跨平台运行&#xff1b;拥有分销、代理、团购秒杀、接龙、拼团、直播、优惠券、自定义表单等众多营…

为什么用迭代器调用不了对象中的函数

没加const可以 加了const就不行 我懂了 加了const v的值就不能修改&#xff0c;我的那些函数都可以修改值 应该是 好像不对 有大佬会吗

直通滤波-PassThrough Filter-原理-代码实现

前言 对坐标轴上的上下限进行约束&#xff0c;选取其中符合范围的点云区域使用场景&#xff1a;去除噪声点&#xff0c;关注特定区域&#xff0c;减小计算量 工作流程 假设我们要在 d d d 轴&#xff08; d ∈ { x , y , z } d \in \{x, y, z\} d∈{x,y,z} &#xff09;上…

yolov5足球运动分析-速度分析-足球跟踪

足球分析项目 引言 在现代体育分析领域&#xff0c;利用先进的计算机视觉技术和机器学习模型对比赛视频进行深入解析已成为一种趋势。本项目旨在通过YOLO&#xff08;You Only Look Once&#xff09;这一顶级的人工智能目标检测模型来识别并跟踪足球比赛中的球员、裁判以及足球…

软件开发详解:通过源码搭建高效的食堂采购与供应链管理平台

通过源码构建定制化的系统&#xff0c;能够让企业根据自身需求灵活调整功能&#xff0c;打造符合其业务流程的高效管理平台。接下来&#xff0c;小编将详细介绍如何通过源码搭建一套高效的食堂采购与供应链管理平台&#xff0c;并分析其在技术架构、功能实现及优化策略方面的关…

大模型入门 ch04:实现一个GPT模型

本文是github上的大模型教程LLMs-from-scratch的学习笔记&#xff0c;教程地址&#xff1a;教程链接 LLM大模型主要是参数量大&#xff0c;而不是代码量大。 这是本节的具体内容 首先实现一个GPT的骨架分别实现GPT骨架内的各个部分&#xff0c;包括LayerNorm&#xff0c;GELU,…

有什么好用的电容笔?2024总结apple pencil平替笔排名TOP五!

在这个信息高度发展的社会&#xff0c;iPad等触控设备日益普及&#xff0c;电容笔的市场需求也不断扩大&#xff0c;因为它们在一定程度上可以替代传统的笔和纸&#xff0c;携带它们就无需携带厚重的书本&#xff0c;这种环保、便捷、方便的特点吸引了越来越多的用户。但电容笔…

动态线程池(五)

动态线程池 Filter过滤器 AlarmBaseFilter NoticeBaseFilter NotifyRedisTateLimiterFilter RedisRateLimiter redis限流器 NotifierHandler DtpNotifier动态线程池通知者 Notifier通知者 关于发送Email消息的额外说明

分布式Id生成策略-美团Leaf

之前在做物流相关的项目时候&#xff0c;需要在分布式系统生成运单的id。 1.需求&#xff1a; 1.全局唯一性&#xff1a;不能出现重复的ID。&#xff08;基本要求&#xff09; 2.递增&#xff1a;大多数关系型数据库&#xff08;如 MySQL&#xff09;使用 B 树作为索引结构。…

三菱FX3U-4DA(4通道模拟量输出)使用说明

FX3U-4DA连接在FX3G/FX3GC/FX3U/FX3UC可编程控制器上&#xff0c;是将来自可编程控制器的4个通道的数字值转换成模拟量值(电压/电流)并输出的模拟量特殊功能模块。 1、FX3G/FX3GC/FX3U/FX3UC可编程控制器上最多可以连接8台*1(包括其它特殊功能模块的连接台数。) 2、可以对各通道…

Global Attention Decoder for Chinese Spelling Error Correction(ACL2021)

Global Attention Decoder for Chinese Spelling Error Correction(ACL2021) 一.概述 作者认为现有的纠错方法大多是基于局部上下文信息进行纠错&#xff0c;没有考虑句子中错词的影响。将注意力放在错误上下文信息上可能会误导并降低CSC(Chinese Spelling Correction)的整体性…

shopro前端 短信登录只显示模板不能正常切换

删掉 换成下面的代码 // 打开授权弹框 export function showAuthModal(type smsLogin) {const modal $store(modal);setTimeout(() > {modal.$patch((state) > {state.auth type;});}, 100); }

数据集 InterHand2.6M 双手交互 三维手势建模 >> DataBall

数据集 InterHand2.6M 双手交互 三维手势建模 人工智能 深度学习 >> DataBall 数据集 InterHand2.6M&#xff0c;双手/单手交互 ---------------------------------------------------------------------------------------------------------- Train set * Train (H):…

MybatisPlus代码生成器使用

一、前言 Mybatis逆向工程也可以生成代码&#xff0c;但配置太过复杂&#xff0c;不便于后期维护&#xff0c;Mybatis Plus 主动集成了代码的自动生成&#xff0c;用起来也很方便&#xff0c;两种代码自动生成我都用过&#xff0c;没有好坏之分&#xff0c;如果非要我推荐哪一…

跨游戏引擎的H5渲染解决方案(腾讯)

本文是腾讯的一篇H5 跨引擎解决方案的精炼。 介绍 本文通过实现基于精简版的HTML5&#xff08;HyperText Mark Language 5&#xff09;来屏蔽不同引擎&#xff0c;平台底层的差异。 好处&#xff1a; 采用H5的开发方式&#xff0c;可以将开发和运营分离&#xff0c;运营部门自…