好久以前做的题，还是值得写一写的。
每次询问的是 \(u,v\) 两点间的所有路径中，边权的最小值最大是多少。
（为了方便，下面写复杂度的时候把 \(n\)，\(m\)，\(q\) 全部写成\(n\)）。
算法1
将图中的边按照边权从大到小的顺序加入，直到两个点 \(u\) 和 \(v\) 能够连通时，最后加入的那条边的边权就是\((u,v)\)这个询问的答案。并查集维护连通性。
我们考虑离线处理。
具体地说，我们每加入一条边时，去遍历这条边所连接了的两个连通块中较小的那个中每个点 \(u\) ，看与 \(u\) 有关的所有询问 \((u,v)\) 中，哪些的 \(v\) 在另一个连通块中，那么这些询问的答案就是刚加入的这条边的权值。
我们发现要支持遍历并查集的操作，虽然可以稍微改造一下一般的并查集来实现，但是启发式合并 vector 可以很容易地实现这样的功能。具体见代码。
由于是启发式合并，总时间复杂度为 \(O(n\log n)\)，空间复杂度也是 \(O(n\log n)\) 。可以通过。
#include<cstdio>
#include<algorithm>
#include<vector>
const int N=10003,Q=30003,M=50003;
int n,m,q,ans[Q],p[N],siz[N];
struct edge{int u,v,c;}g[M];
bool Cmp(const edge&a,const edge&b){return a.c>b.c;}
struct query{int v,p;};std::vector<query>h[N];
std::vector<int>t[N];
int main(){
int u,v,x,y,tmp;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].c);
std::sort(g+1,g+1+m,Cmp);
scanf("%d",&q);
for(int j=1;j<=q;j++){
scanf("%d%d",&u,&v);
h[u].push_back((query){v,j}),h[v].push_back((query){u,j});
ans[j]=-1;
}
for(u=1;u<=n;u++)p[u]=u,t[u].push_back(u),siz[u]=1;
for(int i=1;i<=m;i++)if((u=p[g[i].u])!=(v=p[g[i].v])){
if(siz[u]>siz[v])tmp=u,u=v,v=tmp;
for(int j=0;j<t[u].size();j++){
x=t[u][j];
for(int j=0;j<h[x].size();j++)
if(p[h[x][j].v]==v)ans[h[x][j].p]=g[i].c;
}
for(int j=0;j<t[u].size();j++)
t[v].push_back(t[u][j]),p[t[u][j]]=v;
siz[v]+=siz[u];
}
for(int j=1;j<=q;j++)printf("%d\n",ans[j]);
return 0;
}算法2
其实，我们会发现这个过程和 Kruskal 算法求最大生成树是一样的。
所以\(u\)，\(v\)之间满足边权的最小值最大的路径一定在图的最大生成树上——实际上，由于图不保证连通，这其实是一个最大生成森林。
于是先建出图的最大生成森林，然后用倍增或者树链剖分的技巧快速求出路径上的最小边。这种做法时间复杂度是 \(O(n\log n)\)，可以通过。
#include<cstdio>
#include<algorithm>
using namespace std;
int read(){
int a=0;char c=getchar();
while(c<48||c>57)c=getchar();while(c>47&&c<58)a=a*10+c-48,c=getchar();
return a;
}
struct edge{int u,v,c;}e[50000];
bool cmp(edge a,edge b){return a.c>b.c;}
struct node{int v,c,nxt;}mst[20000];
int n,m,p[10000],head[10000],k,d[10000],f[10000][14],mn[10000][14];
int Insert(int u,int v,int c){mst[++k]=(node){v,c,head[u]};head[u]=k;}
int Find(int a){return p[a]==a?a:p[a]=Find(p[a]);}
int Mst(){
sort(e,e+m,cmp);
for(int i=0;i<m;i++)if(Find(e[i].u)!=Find(e[i].v)){
p[Find(e[i].u)]=Find(e[i].v);
Insert(e[i].u,e[i].v,e[i].c);Insert(e[i].v,e[i].u,e[i].c);
}
}
int dfs(int u){
int v;
for(int i=head[u];i;i=mst[i].nxt)if(!d[v=mst[i].v])
d[v]=d[u]+1,f[v][0]=u,mn[v][0]=mst[i].c,dfs(v);
}
int Pathmin(int u,int v){
int s=1e9;
if(d[u]<d[v])u^=v,v^=u,u^=v;
for(int i=d[u]-d[v],k=0;i;i>>=1,k++)
if(i&1)s=min(s,mn[u][k]),u=f[u][k];
if(u==v)return s;
for(int i=13;~i;i--)
if(f[u][i]!=f[v][i])
s=min(s,min(mn[u][i],mn[v][i])),u=f[u][i],v=f[v][i];
return min(s,min(mn[u][0],mn[v][0]));
}
int main(){
int u,v;
n=read();m=read();
for(int i=1;i<=n;i++)p[i]=i;
for(int i=0;i<m;i++)
e[i].u=read(),e[i].v=read(),e[i].c=read();
Mst();
for(int i=1;i<=n;i++)if(!d[i])d[i]=1,dfs(i);
for(int j=1;j<=13;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1],mn[i][j]=min(mn[i][j-1],mn[f[i][j-1]][j-1]);
m=read();
while(m--){
u=read();v=read();
if(Find(u)!=Find(v))puts("-1");
else printf("%d\n",Pathmin(u,v));
}return 0;
}原文：https://www.cnblogs.com/Camp-Nou/p/11815712.html