（MST，并查集）nflsoj #4114 货车运输/洛谷 P1967NOIP2003 货车运输

题意

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

$1\le n<10^4$，$1\le m<5\times 10^4$，$1\le q<3\times 10^4$，$0\le z\le 10^5$。

思路

这是一道很经典的题目。

考虑转化题意，运输的最大重量就是，司机经过的边的限重值的最小值。（这很有二分特征，可以整体二分做，不过现在不用这个做法）

我们对这个无向图跑出一棵最大生成树，司机在树边上跑，肯定比跑其它的边更优呢！

于是就变成了，求 $u\to v$ 的树上路径最小值。首先肯定要维护做 lca 的倍增数组了，类似地，我们维护一个倍增形式的最小值数组，记 $m{i}_{i,k}$ 表示 $i\to i$ 的 $2^k$ 级祖先路上的边权最小值。求 lca 跳的时候可以一边跳祖先一边求最小值。

时间复杂度 $O(m\log m+q\log n)$，分别是对边排序和查询时在线求 lca，这个经典的做法常数很小，看洛谷 P8240 偷铀计划的提交记录就知道了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e4+9,inf=0x7f7f7f7f;
ll n,m,Q;
struct bian
{ll u,v,w;
}b[N<<1];
bool cmp(bian x,bian y)
{return x.w>y.w;
}
ll fa[N];
ll fz(ll x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;
}
struct edge
{ll to,next,w;
}e[N<<1];
ll idx,head[N];
void addedge(ll u,ll v,ll w)
{idx++;e[idx].to=v;e[idx].next=head[u];e[idx].w=w;head[u]=idx;
}
void kruskal()
{ll tot=0;for(int i=1;i<=m;i++){ll u=b[i].u,v=b[i].v,w=b[i].w;ll fu=fz(u),fv=fz(v);if(fu==fv)continue;fa[fv]=fu;addedge(u,v,w);addedge(v,u,w);tot++;if(tot==n-1)break;}
}
ll dep[N],f[N][16],mi[N][16];//u到(1<<i)级父亲路上最小w 
bool vis[N];
void dfs(ll u,ll fa)
{vis[u]=1;if(fa==0){dep[u]=1;mi[u][0]=inf;}for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;f[v][0]=u;mi[v][0]=w;dep[v]=dep[u]+1;for(int j=1;(1<<j)<=dep[v];j++){f[v][j]=f[f[v][j-1]][j-1];//提前更新v mi[v][j]=min(mi[v][j-1],mi[f[v][j-1]][j-1]);//	cout<<mi[v][j-1]<<" "<<mi[f[v][j-1]][j-1]<<endl;	}dfs(v,u);}
}
ll lca_cal(ll x,ll y)
{ll ret=inf;if(dep[x]<dep[y])swap(x,y);for(int i=15;i>=0;i--){if(dep[x]-(1<<i)>=dep[y]){ret=min(ret,mi[x][i]);//先更新，不然少算 f[x][i]~x x=f[x][i];}}if(x==y)return ret;for(int i=15;i>=0;i--){if(f[x][i]!=f[y][i]){ret=min(ret,min(mi[x][i],mi[y][i]));x=f[x][i];y=f[y][i];}}ret=min(ret,min(mi[x][0],mi[y][0]));return ret;
}
int main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);b[i]=(bian){u,v,w};}sort(b+1,b+m+1,cmp);for(int i=1;i<=n;i++)fa[i]=i;kruskal();for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0);scanf("%lld",&Q);while(Q--){ll u,v;scanf("%lld%lld",&u,&v);if(fz(u)!=fz(v))puts("-1");else printf("%lld\n",lca_cal(u,v));}return 0;
}