题解 P1967 【货车运输】
NaCly_Fish
·
·
题解
终于把这题切了。。百感交集啊
听说 NOIp 前发题解可以 rp++，于是就有了这篇题解
首先我们来分析：
要使得货车装最重的货物，那么就必须货车走的路载重要尽可能大 —— 也就是说，载重较小的路是不会被走过的。
于是我们就可以想到构建一棵原图的最大生成树（参见模板 P3366 最小生成树）。这样就可以在满足各城市之间连通情况不变的前提下，使得城市之间路载重最大。
然后：求货车能装最大货物重量的问题，就转化成了求树上两点权值最小的边的问题了！
如果用朴素算法求的话，显然是不行的，单次查询会被卡到 \mathcal O(n) 的复杂度。
那我们可以换一种思路：倍增求出 u,v 两点的 LCA，设其为 t。
那么 u 到 v 的最小边权就是：u 到 t 的最小边权 和 v 到 t 的最小边权取较小值。
我们可以建一个数组 `minw`（即 Minimum Weight），其中 `minw[i][j]` 表示 $i$ 节点到其 $2^j$ 级祖先之间的最小边权。是不是和倍增 LCA 的做法很像？
这样就可以在求 LCA 的过程中得到答案了。
我们也容易推出 `minw` 的递推公式：
（为了方便，这里设 $i$ 的 $2^j$ 级祖先为 $g$）
```cpp
minw[i][j] = min(minw[i][j-1],minw[g][j-1]);
```
有了递推公式，`minw` 数组就可以在预处理节点祖先信息时搞定了。
****
最后就是计算答案的部分：
对于不连通的两个点很好判断，用并查集判一下，如果不连通直接输出 $-1$。
如果两点连通：
我们需要记录答案 `ans` ，并初始化为正无穷（取一个足够大的整数即可）。
对于点 $u$，倍增过程中每次跳到其 $2^j$ 级节点时，进行操作：
```cpp
ans = min(ans,minw[u][j]);
```
这样你就得到了答案！
注意坑点：
给定的图可能有一些互不连通的城市群，在预处理的时候不要遗漏了。
参考代码：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 10003
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int u,v,w;
edge(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
bool operator < (const edge& a) const{
return w>a.w;
}
};
int f[N][15],depth[N],lg2[N];
int ft[N],minw[N][15];
bool vis[N];
vector<edge> adj[N];
edge e[50003];
int n,m;
inline int min(int a,int b){
if(a>b) return b;
return a;
}
int find(int x){
if(ft[x]==x) return x;
ft[x] = find(ft[x]);
return ft[x];
}
inline void read(int &x){
x = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
x = (x<<3)+(x<<1)+c-'0';
c = getchar();
}
}
inline int getw(int u,int v){
int l = adj[u].size();
for(int i=0;i<l;++i){
if(v==adj[u][i].v)
return adj[u][i].w;
}
}
void dfs(int u,int fa){
vis[u] = true;
depth[u] = depth[fa]+1;
f[u][0] = fa;
int w,g,v,l,t = lg2[depth[u]];
w = getw(u,fa);
minw[u][0] = w;
if(fa==0) minw[u][0] = inf;
for(int i=1;i<t;++i){
g = f[u][i-1];
minw[u][i] = min(minw[u][i-1],minw[g][i-1]);
f[u][i] = f[g][i-1];
}
l = adj[u].size();
for(int i=0;i<l;++i){
v = adj[u][i].v;
if(v==fa) continue;
dfs(v,u);
}
}
int lca(int a,int b){
if(find(a)^find(b)) return -1;
int t,res = inf;
if(depth[a]<depth[b]){
t = a;
a = b;
b = t;
}
while(depth[a]>depth[b]){
t = lg2[depth[a]-depth[b]]-1;
res = min(res,minw[a][t]);
a = f[a][t];
}
if(a==b) return res;
for(t=lg2[depth[a]]-1;t>=0;--t){
if(f[a][t]==f[b][t]) continue;
res = min(res,min(minw[a][t],minw[b][t]));
a = f[a][t];
b = f[b][t];
}
res = min(res,min(minw[a][0],minw[b][0]));
return res;
}
void kruskal(){
sort(e+1,e+1+m);
int cnt = n-1;
for(int i=1;i<=m;++i){
if(cnt==0) break;
int fu,fv,u,v,w;
u = e[i].u;
v = e[i].v;
w = e[i].w;
fu = find(u);
fv = find(v);
if(fu==fv) continue;
ft[fu] = fv;
--cnt;
adj[u].push_back(edge(u,v,w));
adj[v].push_back(edge(v,u,w));
}
}
int main(){
memset(minw,inf,sizeof(minw));
int u,v,w,q;
read(n),read(m);
for(int i=1;i<=n;++i) ft[i] = i;
for(int i=1;i<=m;++i){
read(u),read(v),read(w);
e[i] = edge(u,v,w);
}
kruskal();
lg2[1] = 1;
for(int i=2;i<=n;++i)
lg2[i] = lg2[i-1]+(i>>lg2[i-1]==1);
for(int i=1;i<=n;++i){
if(vis[i]) continue;
dfs(i,0);
}
read(q);
++q;
while(--q){
read(u),read(v);
printf("%d\n",lca(u,v));
}
return 0;
}
```