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

news/2024/9/25 5:41:14/

*原题链接*

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

先简化题意,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.ppmy.cn/news/1530146.html

相关文章

9.24作业

将昨天的My_string类中的所有能重载的运算符全部进行重载 、[] 、>、<、、>、<、! 、&#xff08;可以加等一个字符串&#xff0c;也可以加等一个字符&#xff09;、输入输出(<< 、 >>) 代码如下 MyString.h #ifndef MYSTRING_H #define MYSTRING_…

智能Ai语音机器人的应用价值有哪些?

随着时间的推移&#xff0c;人工智能的发展越来越成熟&#xff0c;智能时代也离人们越来越近&#xff0c;近几年人工智能越来越火爆&#xff0c;人工智能的应用已经开始渗透到各行各业&#xff0c;与生活交融&#xff0c;成为人们无法拒绝&#xff0c;无法失去的一个重要存在。…

Qt日志输出及QsLog日志库

目录 Qt日志输出及QsLog日志库日志输出格式化日志普通格式化条件格式化环境变量设置格式化日志输出位置日志输出对象信息禁用输出 QsLog日志库使用方法1. 将QsLog目录添加到项目中2. 配置CMakeLists.txt文件3. 配置.pro文件4. 日志记录器的配置5. 运行程序6. 启用行号和文件名C…

【计算机网络 - 基础问题】每日 3 题(二十)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏&…

性能监控之Python实战SkyWalking链路追踪

文章目录 一、介绍二、SkyWalking支持的语言三、SkyWalking安装3.1 前提准备3.2 先安装ElasticSearch7.X3.3 Skywalking-OAP 安装3.4 Skywalking-UI 界面安装3.5 访问页面检查SkyWalking是否可以访问 四、Python 项目接入SkyWalking4.1 演示项目代码4.2 验证 sw-python4.3 配置…

关于wordPress中的用户登录注册等问题

前言 大家在做类似的功能的时候&#xff0c;有没有相关的疑问。那就是我都已经选择好了相应的主题和模版&#xff0c;但是为什么都没有用户注册和用户登录的页面存在呢&#xff1f; WordPress默认情况下不提供用户注册和登录功能的原因是它最初是作为一个博客平台开发的&…

AjAX(简介以及一些用法)

AJAX 1. 简介 什么是 Ajax Ajax 的全称是 Asynchronous JavaScript And XML &#xff08;异步 JavaScript 和 XML &#xff09;我们可以理解为&#xff1a;在网页中 利用 XMLHttpRequest 对象和服务器进行数据交互的方式就是 Ajax &#xff0c;它可以帮助我们轻松实现网页…

Python画笔案例-059 绘制甩曲彩点动图

1、绘制甩曲彩点动图 通过 python 的turtle 库绘制 甩曲彩点动图,如下图: 2、实现代码 绘制甩曲彩点动图,以下为实现代码: """甩曲彩点动图.py """ import time import turtlecs = [red,orange,