洛咕
题意:A国有n座城市，编号从1到n，城市之间有m条双向道路.每一条道路对车辆都有重量限制，简称限重.现在有q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物?
分析:题意就是找到给定两点之间的一条路径,使得最小边权最大.所以我们先构建出图的一棵最大生成树(因为图可能不连通,可能n个点会变成森林).然后在每棵最大生成树上(dfs)预处理出(f[i][j],dis[i][j])分别表示节点(i)的(2^j)级祖先,节点(i)到(2^j)级祖先路径上的最小边权.
然后对于每组询问,就直接查询(LCA),节点在往上跳找(LCA)的时候,通过(dis)数组记录找到答案.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=10005;
const int M=50005;
int n,m,visit[N];
int fa[N],f[N][25],dep[N],dis[N][25];
int tot,head[N],nxt[M],to[M],w[M];
struct ppx{int x,y,z;}a[M];
inline bool cmp(ppx x,ppx y){return x.z>y.z;}
inline int get(int x){
if(x==fa[x])return x;
return fa[x]=get(fa[x]);
}
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;to[tot]=b;w[tot]=c;
nxt[++tot]=head[b];head[b]=tot;to[tot]=a;w[tot]=c;
}
inline void kruskal(){
sort(a+1,a+m+1,cmp);//边权从大到小排序,就是最大生成树了
for(int i=1;i<=n;++i)fa[i]=i;
for(int i=1;i<=m;++i){
int x=get(a[i].x),y=get(a[i].y);
if(x==y)continue;
fa[x]=y;add(x,y,a[i].z);
}
}
inline void dfs(int u,int fa){
visit[u]=1;
for(int j=1;j<=20;++j){
f[u][j]=f[f[u][j-1]][j-1];
dis[u][j]=min(dis[u][j-1],dis[f[u][j-1]][j-1]);
}
for(int i=head[u];i;i=nxt[i]){
int v=to[i];if(v==fa)continue;
f[v][0]=u;dis[v][0]=w[i];
dep[v]=dep[u]+1;dfs(v,u);
}
}
inline int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int j=20;j>=0;--j)
if(dep[f[x][j]]>=dep[y])x=f[x][j];
if(x==y)return x;
for(int j=20;j>=0;--j)
if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
return f[x][0];
}
int main(){
memset(dis,0x3f,sizeof(dis));
n=read();m=read();
for(int i=1;i<=m;++i)a[i].x=read(),a[i].y=read(),a[i].z=read();
kruskal();
for(int i=1;i<=n;++i)if(!visit[i])dfs(i,0);//可能是森林,所以要对每个没有访问到的点dfs
int Q=read();
while(Q--){
int x=read(),y=read(),ans=1e9;
if(get(x)!=get(y)){puts("-1");continue;}//特判,不在一棵树内,即不连通
int lca=LCA(x,y);if(!lca)lca=1;
for(int j=20;j>=0;--j){
if(dep[f[x][j]]>=dep[lca]){
ans=min(ans,dis[x][j]);
x=f[x][j];
}
if(dep[f[y][j]]>=dep[lca]){
ans=min(ans,dis[y][j]);
y=f[y][j];
}
}
printf("%d
",ans);
}
return 0;
}