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;
}