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

ops/2024/9/22 17:51:34/

*原题链接*

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

先简化题意,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/ops/114353.html

相关文章

JSON.parseArray 内存溢出

实际上我的JSON如下&#xff1a; 如果用以下代码&#xff1a;JVM的内存直接飙到内存溢出&#xff0c;报错OutOfMemoryError: Java heap space Object oo JSON.parseArray(json, TestVo.class) 如果我换成了这样&#xff0c;就没事&#xff1a; Object oo JSON.parseObject(…

MISC - 第一天(stegsolve图片隐写解析器、QR research、binwalk,dd文件分离,十六进制文件编辑器)

前言 各位师傅大家好&#xff0c;我是qmx_07&#xff0c;最近更新Buuctf在线测评中的MISC杂项内容 介绍 BUUCTF:https://buuoj.cn/ &#xff0c;整合了各大 CTF 赛事题目&#xff0c;类型丰富&#xff0c;涵盖了Web 安全、密码学、系统安全、逆向工程、代码审计等多个领域 …

VUE面试题(单页应用及其首屏加载速度慢的问题)

目录 一、单页应用 1.概念 2.单页面应用的优缺点 二、多页面应用&#xff1a; 1.概念 2.区别 三、SPA的实现 1.原理 2.方式&#xff1a; 3.Hash与History模式有什么区别 四、首屏加载速度慢如何优化 1.什么是首屏加载&#xff1f; 2.首屏加载慢的原因 3.如何解决…

Qt 学习第十天:小项目:QListWidget的使用

一、页面布局 二、命名按钮 双击按钮可以修改显示中的文字&#xff08;例如&#xff1a;改成“全选”&#xff09;&#xff0c;objectName是要改成程序员所熟悉的名字&#xff08;英文&#xff0c;符合代码规范&#xff09;方便修改和书写代码&#xff0c;一看就能看懂的 三、…

使用IDA Pro动态调试Android APP

版权归作者所有&#xff0c;如有转发&#xff0c;请注明文章出处&#xff1a;https://cyrus-studio.github.io/blog/ 关于 android_server android_server 是 IDA Pro 在 Android 设备上运行的一个调试服务器。 通过在 Android 设备上运行android_server&#xff0c;IDA Pro …

Mybatis的XML实现方法

Mybatis的开发有两种方式&#xff1a; 1、注解 2、XML 使用Mybatis的注解方式&#xff0c;主要是来完成一些简单的增删改查功能。如果需要实现复杂的SQL功能&#xff0c;建议使用XML来配置映射语句&#xff0c;也就是将SQL语句写在XML配置文件中。 Mybatis的XML的实现需要以下…

Android 开发高频面试题之——Flutter

Android开发高频面试题之——Java基础篇 flutter高频面试题记录 Flutter1. dart中的作用域与了解吗2. dart中. .. ...分别是什么意思?3. Dart 是不是单线程模型?如何运行的?4. Dart既然是单线程模型支持多线程吗?5. Future是什么6. Stream是什么7. Flutter 如何和原生交互…

【Pycharm】Pycharm创建Django提示pip版本需要升级

目录 1、现象 2、分析 3、本质 前言&#xff1a;经常使用pycharm创建django、flask等项目时候提示pip版本需要升级&#xff0c;解决方案 1、现象 使用Pycharm创建Django项目提示安装Django超时&#xff0c;报错建议pip升级22升级到24 2、分析 之前使用命令升级了pip到了24…