A220题解

题目分析
本题是一道最大生成树 + 树上倍增 LCA的综合应用题。
货车在两点间运输的最大载重，等价于两点间所有路径中最小边权的最大值，这是经典的瓶颈路径问题。
最大生成树能保留图中所有节点的连通性，且任意两点间的唯一路径，就是原图中瓶颈路径（最小边权最大的路径）。因此我们先构建图的最大生成树，再通过树上倍增预处理树的信息，快速查询每对节点间路径的最小边权，即为答案；若两点不连通，输出 - 1。

算法思路
1.Kruskal 算法构建最大生成树
将所有边按权值从大到小排序，用并查集维护连通性，依次加入不形成环的边，最终得到最大生成树。
2.树上倍增预处理
通过 DFS 遍历生成树，预处理每个节点的2^k 级祖先和到 2^k 级祖先路径上的最小边权，同时记录节点深度。
3.倍增 LCA 查询答案
对于每组查询，先判断两点是否连通；若连通，利用倍增法找到两点的最近公共祖先，同步计算路径上的最小边权，即为最大载重。

实践效果
最大生成树将原图的多路径问题简化为树的单一路径问题，保证查询结果为最优解。
最终查询函数直接返回路径最小边权，不连通返回 - 1，匹配题目要求。

示例代码

#include<bits/stdc++.h>
using namespace std;
// LOG：LCA倍增的层数，2^20足够覆盖1e4深度
const int LOG=20;
// 城市最大数量
const int N=1e4+5;
// 道路最大数量
const int M=5e4+5;
// 原始道路结构体：存储 起点u、终点v、限重w
struct ysy{
	int u,v,w;
}e[M];
// 树边结构体：存储 邻接点to、边上的权值val（限重）
struct tree{
	int to,val; 
};
// 邻接表：存储最大生成树
vector<tree> t[N];
// 并查集数组：fa[i] 表示i的父节点
int fa[N];
/*倍增数组：
up[u][i]：u节点向上跳2^i步到达的节点
maxw[u][i]：u节点向上跳2^i步 路径上的最小限重（答案就是路径最小限重）
depth[u]：u节点在树中的深度*/
int up[N][LOG],maxw[N][LOG],depth[N];
// n=城市数 m=道路数 q=询问数
int n,m,q;

void init(int n){
	for(int i=1;i<=n;i++)
		fa[i]=i;
}

int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

bool cmp(const ysy &a,const ysy &b){
	return a.w>b.w;
}

/*构建最大生成树：
因为两点间路径最大载重 = 路径上最小限重
要让这个最小值尽可能大 → 必须用最大生成树*/
void MST(){
	sort(e,e+m,cmp);// 边按限重从大到小排序
	init(n);
	int cnt=0; // 记录已选边数
	for(int i=0;i<m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		// 如果不连通，就加入这条边
		if(find(u)!=find(v)){
			fa[find(u)]=find(v);
			// 加入树的邻接表
			t[u].push_back({v,w});
			t[v].push_back({u,w});
			cnt++;
			// 选够n-1条边，生成树完成
			if(cnt==n-1) return;
		}
	}
}

// DFS预处理倍增数组
// u：当前节点 f：父节点 w：父节点到当前节点的边权
void dfs(int u,int f,int w){
	// 第一步：初始化跳1步（2^0）的信息
	up[u][0]=f;          // u向上跳1步到f
	maxw[u][0]=w;        // 这条边的限重
	depth[u]=depth[f]+1; // 深度=父深度+1
	// 第二步：预处理所有2^i步的跳跃（倍增核心）
	for(int i=1;i<LOG;i++){
		up[u][i]=up[up[u][i-1]][i-1];
		// 路径最小限重 = 两段路径的最小值
		maxw[u][i]=min(maxw[u][i-1],maxw[up[u][i-1]][i-1]);
	}
	// 第三步：遍历子树，继续DFS
	for(auto &p:t[u]){
		int v=p.to,val=p.val;
		if(v!=f) dfs(v,u,val);
	}
}

// 查询x到y的最大载重 = 路径上最小限重
int query(int u,int v){
	// 不在同一连通块 → 无法到达，返回-1
	if(find(u)!=find(v)) return -1;
	int res=INT_MAX; // 记录路径最小限重（答案）
	// 统一让u更深，方便操作
	if(depth[u]<depth[v]) swap(u,v);
	// 第一步：把u向上跳，直到和v同深度
	for(int i=LOG-1;i>=0;i--){
		if(depth[up[u][i]]>=depth[v]){
			res=min(res,maxw[u][i]);
			u=up[u][i];
		}
	}
	// 已经相遇，直接返回答案
	if(u==v) return res;
	// 第二步：u和v一起向上跳，直到祖先相同
	for(int i=LOG-1;i>=0;i--){
		if(up[u][i]!=up[v][i]){
			res=min(res,maxw[u][i]);
			res=min(res,maxw[v][i]);
			u=up[u][i];
			v=up[v][i];	
		}
	}
	// 最后一步：加上最后一步的边权
	res=min(res,maxw[u][0]);
	res=min(res,maxw[v][0]);
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m; 
	for(int i=0;i<m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	MST();
	memset(maxw,0x3f,sizeof(maxw));
	dfs(1,0,0);
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		cout<<query(x,y)<<'\n';
	}
	return 0;
}

复杂度分析
时间复杂度：
O(mlogm+nlogn+qlogn)，mlogm为边排序时间，nlogn为 DFS 预处理时间，qlogn为查询总时间。
空间复杂度：
O(nlogn+m)，主要为倍增数组和邻接表开销。

易错点提醒
1.最大生成树必须按边权降序排序，若升序会变成最小生成树，答案错误。
2.倍增数组maxw存储的是路径最小边权，转移时必须用min更新。
3.DFS 初始化时，根节点的父节点设为 0，边权初始值要正确赋值。
4.查询时必须先判断两点是否在同一连通块，否则直接返回 - 1。

sx : aaa算是第一次公开发题解，刚注册的ACGO，初来乍到的初中生，还请多多包容和指点！
可以在我的团队看看孩子别的题解（平时周156上线）