P9235 [蓝桥杯 2023 省 A] 网络稳定性
最小瓶颈生成树题，和货车运输完全一样。
先简化题意， 次询问，每次给出
，问
到
的所有路径集合中，最小边权的最大值。
对于这种题可以用kruskal生成树来做，也可以用倍增来写，但不管怎样都要先求出最大生成树，因为最小边权的最大值肯定会在最大生成树中出现。然后我们要做的就是在树中，求 到
的最短路径上的最小边权。这个可以倍增求，求解的过程类似求 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;
}原文地址：https://blog.csdn.net/summ1ts/article/details/142424294
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！