题意简述
给定一个\(N\)个节点，\(M\)条边的无向图，其中每条边有一个边权。
接下来给定\(q\)次询问。每次询问给出\(x,y\)，请计算\(x\)到\(y\)路径上最小边权的最大值是多少。
解题思路
我们对于每个连通块跑一遍最大生成树。这样整张图就成了一片森林。
接下来对于森林里的每一棵树，跑一遍LCA，顺便维护\(minn[pos][n]\)表示\(pos\)向上\(2^n\)层的最小边权。查询时，每跳一步更新最小边权，最终返回最小边权即可。
时间复杂度\(O(m\log m+q\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define N 10010
#define M 50010
using namespace std;
int n,m,q,ffa[N],dep[N],fa[N][20],minn[N][20];
//ffa用于并查集，fa用于LCA
bool vis[N];
struct tedge{int u,v,w;}edges[M];
bool cmp(tedge a,tedge b){return a.w>b.w;}
int find(int x){
if(ffa[x]==x) return x;
return ffa[x]=find(ffa[x]);
}
struct edge{int to,w;};
vector<edge> G[N];
void dfs(int u,int father){
vis[u]=1;
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=1;i<20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1],
minn[u][i]=min(minn[u][i-1],minn[fa[u][i-1]][i-1]);
for(auto i:G[u])
if(i.to!=father){
minn[i.to][0]=i.w;
dfs(i.to,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int ans=INT_MAX;
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])
ans=min(ans,minn[u][i]),
u=fa[u][i];
if(u==v) return ans;
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
ans=min(ans,min(minn[u][i],minn[v][i])),
u=fa[u][i],v=fa[v][i];
ans=min(ans,min(minn[u][0],minn[v][0]));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) ffa[i]=i;
for(int i=1;i<=m;i++)
cin>>edges[i].u>>edges[i].v>>edges[i].w;
sort(edges+1,edges+1+m,cmp);
for(int i=1;i<=m;i++){
int u=find(edges[i].u),v=find(edges[i].v);
if(u==v) continue;
ffa[u]=v;
G[edges[i].u].push_back({edges[i].v,edges[i].w});
G[edges[i].v].push_back({edges[i].u,edges[i].w});
}
for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
if(find(x)!=find(y)) cout<<"-1\n";
else cout<<lca(x,y)<<"\n";
}
return 0;
}