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

server/2024/9/25 3:09:45/

*原题链接*

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

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

相关文章

《线性代数》学渣笔记

文章目录 1 行列式1.1 克拉默法则1.2 基本性质1.3 余子式 M i j M_{ij} Mij​1.4 代数余子式 A i j ( − 1 ) i j ⋅ M i j A_{ij} (-1)^{ij} \cdot M_{ij} Aij​(−1)ij⋅Mij​1.5 具体型行列式计算&#xff08;化为基本型&#xff09;1.5.1 主对角线行列式&#xff1a;主…

FPGA-Vivado-IP核-虚拟输入输出(VIO)

VIO IP核 背景介绍 Vivado中的VIO&#xff08;Virtual Input/Output&#xff0c;虚拟输入/输出&#xff09; IP核是一种用于调试和测试FPGA设计的IP核。当设计者通过JTAG接口与FPGA芯片连接时&#xff0c;在Vivado的Verilog代码中添加VIO IP核&#xff0c;就可以让设计者与FPG…

BERT训练环节(代码实现)

1.代码实现 #导包 import torch from torch import nn import dltools #加载数据需要用到的声明变量 batch_size, max_len 1, 64 #获取训练数据迭代器、词汇表 train_iter, vocab dltools.load_data_wiki(batch_size, max_len) #其余都是二维数组 #tokens, segments, vali…

2024全国研究生数学建模竞赛(数学建模研赛)ABCDEF题深度建模+全解全析+完整文章

全国研究生数学建模竞赛&#xff08;数学建模研赛&#xff09;于9月21日8时正式开赛&#xff0c;赛程4天半&#xff0c;咱这边会在开赛后第一时间给出对今年的6道赛题的评价、分析和解答。包括ABCDEF题深度建模全解全析完整文章&#xff0c;详情可以点击底部的卡片来获取哦。 …

Big Data 流处理框架 Flink

Big Data 流处理框架 Flink 什么是 FlinkFlink 的主要特性典型应用场景 Amazon Elastic MapReduce (EMR) VS Flink架构和运行时环境实时处理能力开发和编程模型操作和管理应用场景总结 Flink 支持的数据源Flink 如何消费 AWS SQS 数据源自定义 Source FunctionFlink Connector …

【AI大语言模型】提示词工程基础及进阶

【AI大语言模型】提示词工程基础及进阶 什么是提示词&#xff08;Prompt&#xff09; 提示词&#xff08;Prompt&#xff09;是与人工智能对话时用来引导或触发生成某种输出的指令。 它相当于你在与 AI 进行互动时所提出的问题或任务说明。提示词可以是简短的指令、一个问题…

【2025】基于微信小程序的网上点餐系统设计与实现、基于微信小程序的智能网上点餐系统、微信小程序点餐系统设计、智能点餐系统开发、微信小程序网上点餐平台设计

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

微信小程序06-综合项目点餐系统

零、文章目录 微信小程序06-综合项目点餐系统 1、项目开发准备 &#xff08;1&#xff09;开发背景 现如今&#xff0c;相比以服务员为中介完成点餐、送餐、买单的传统点餐方式&#xff0c;越来越多的餐厅开始使用微信小程序进行点餐。商家可以在微信小程序中添加点餐和收款…