T3 货车运输

生成树 + lca + dp

solution

题意就是在图上给定 $q$ 个询问，求 $(u,v)$ 的所有路径中边权最小的边中的最大值

直接在图上求十分困难，考虑贪心。显然，有一些边权较小路径我们是不会经过的，所以可以将这些路径去掉。这时即可以在图上求最大生成树，然后在最大生成树处理询问

于是询问就转化为树上问题，求 $(u,v)$ 路径上最小边权。$(u,v)$ 路径可转化为 $(u,lca_{u,v})$，$(lca_{u,v},v)$ 两条路径，所以可以在求 lca 时处理

借鉴求 lca 的思路，设 $f_{u,i}$ 为从 $u$ 到 $u$ 的 $2^i$ 级祖先路径上最小边权。显然 $f_{u,0} = w(u , fa_u)$，转移如下：

$$f_{u,i} = \min(f_{u , i - 1} , f_{fa_{u , i - 1} , i-1})$$

和 lca 过程中 fa 的转移过程差不多

随后在求 lca 统计最小边权即可。

注意：本题目中所给的图不一定联通，所以要分别对每个连通分量 dfs

code

#include<bits/stdc++.h>
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;

const int N = 1e4 + 5;
const int M = 5e4 + 5;
const int inf = 0x3f3f3f3f;

struct node{
	int to , w;
};

struct edge{
	int x , y , w;
}e[M];

int n , m , q;
int fath[N] , fa[N][20] , dp[N][20] , dis[N] , lg[M] , vis[N];
vector<node> g[N];

bool cmp(const edge &lhs , const edge &rhs){
	return lhs.w > rhs.w;
}

int find(int x){                      // 并查集板子
	if(x == fath[x]) return x;
	return fath[x] = find(fath[x]);
}

bool uni(int x , int y){
	int u = find(x) , v = find(y);
	if(u != v){
		fath[u] = v;
		return true;
	}
	return false;
}

void kruskal(){                         // 求最大生成树
	int cnt = 0;
	sort(e + 1 , e + m + 1 , cmp);
	
	for(int i = 1 ; i <= m ; i ++){
		if(uni(e[i].x , e[i].y)){
			cnt ++;
			g[e[i].x].push_back({e[i].y , e[i].w});
			g[e[i].y].push_back({e[i].x , e[i].w});
		}
		if(cnt >= n - 1) break;
	}
}

void dfs(int u , int f , int w){                            // dfs 倍增预处理
	fa[u][0] = f , dp[u][0] = w , dis[u] = dis[f] + 1 , vis[u] = 1;
	
	for(int i = 1 ; i <= lg[dis[u]] ; i ++){
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
		dp[u][i] = min(dp[u][i - 1] , dp[fa[u][i - 1]][i - 1]);
	}
	for(auto v : g[u]){
		if(v.to != f) dfs(v.to , u , v.w);
	}
}

int lca(int x , int y){                         // 求 lca , ans
	int res = inf;
	if(dis[x] < dis[y]) swap(x , y);
	
	while(dis[x] > dis[y]){
		res = min(res , dp[x][lg[dis[x] - dis[y]] - 1]);
		x = fa[x][lg[dis[x] - dis[y]] - 1];
	}
	if(x == y) return res;
	
	for(int i = lg[dis[x]] - 1 ; i >= 0 ; i --){
		if(fa[x][i] != fa[y][i]){
			res = min(res , min(dp[x][i] , dp[y][i]));
			x = fa[x][i] , y = fa[y][i];
		}
	}
	res = min(res , min(dp[x][0] , dp[y][0]));
	return res;
}

signed main(){              qwq
	cin >> n >> m;
	
	for(int i = 1 ; i <= m ; i ++){
		cin >> e[i].x >> e[i].y >> e[i].w;
	}
	for(int i = 1 ; i <= n ; i ++){
		fath[i] = i;
	}
	kruskal();
	memset(dp , inf , sizeof dp);
	
	for(int i = 1 ; i < M ; i ++){
		lg[i] = lg[i >> 1] + 1;
	}
	for(int i = 1 ; i <= n ; i ++){
		if(!vis[i]) dfs(i , 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;
}

T6 华容道