洛谷题单指南-最小生成树-P1967 [NOIP 2013 提高组] 货车运输
原题链接：https://www.luogu.com.cn/problem/P1967
题意解读：在n个节点的带权无向图中，有q个询问，求两点之间的路径中，最小边的最大值。
解题思路：
1、初步分析
要求两点之间路径中最小边的最大值，可以将kruskal算法变化一下：
从大到小一次处理每条边，当将边u->v连通，此时如果对于一个询问两点a、b是连通的，那么本次加入的u->v的边权值就是答案。
换句话说，要求的是在图的最大生成树中，两点之间路径上的最小边。
2、朴素想法
枚举法1：用变化的kruskal算法，从大到小处理边，连通一条边后，枚举所有询问，如果询问的两点可以连通，更新该询问的答案。复杂度为O(m*n)。
枚举法2：用变化的kruskal算法，先求最大生成树（由于不一定连通，可以添加一个虚拟0点，和其余点连接一条长度为-1的边），再基于最大生成树的边建图，从每一个点开始DFS求出该点到所有点路径上的最小边。复杂度为O(n^2)。
3、优化思路
可以针对枚举法2进行优化。
类似于求严格次小生成树时采用的优化方式，通过LCA和倍增来计算两点之间路径上的最小边。
设fa[i][j]表示i的第2^j个祖先，d[i][j]表示从i往上跳2^j个祖先的路径上的最小边
初始化：d[i][j] = min(d[i][j - 1], d[fa[i][j - 1]][j - 1])
计算：在LCA的过程中，路径上的最小边就是LCA处理中每段区间的最小边
算法步骤：
1、构建最大生成树
使用 Kruskal 算法对图中的边按权值从大到小排序。注意加入虚拟0点。
使用并查集判断是否将一条边加入生成树，若加入，则更新该边是否属于生成树。
对生成树用邻接表建图。
2、构建 LCA 数据结构
使用 DFS 遍历生成树，计算每个节点的深度、父节点以及到父节点路径上的最小边权。
使用倍增法计算每个节点的 2^i 个祖先和路径上的最小边。
3、处理查询
对每一个查询x y，通过 LCA 算法计算从节点x到节点y的路径上的最小边权，并输出结果。
100分代码：
#include <bits/stdc++.h>
using namespace std;
// 常量定义：最大节点数N，最大边数M，INF为无穷大
const int N = 10005, M = 60005, INF = 0x3f3f3f3f;
// 边的结构体
struct Edge
{
int u, v, w; // 边的两个节点u和v，边的权重w
bool intree; // 标记该边是否在生成树中
bool operator < (const Edge &e) const
{
return w > e.w; // 边按权重从大到小排序
}
} edges[M]; // 边集数组
int cnt; // 边数计数器
int p[N]; // 并查集数组，用于判断两个节点是否在同一集合
int h[N], e[M], w[M], ne[M], idx; // 邻接表，h为邻接表头，e为目标节点数组，w为权重数组，ne为下一条边数组，idx为当前边下标
int depth[N], fa[N][14], d[N][14]; // depth为节点深度，fa[i][j]为节点i的2^j父节点，d[i][j]为节点i到2^j父节点路径上的最小边
int n, m, q; // n为节点数，m为边数，q为询问次数
// 向邻接表添加一条边
void add(int a, int b, int c)
{
e[++idx] = b; // 添加目标节点b
w[idx] = c; // 设置边的权重c
ne[idx] = h[a]; // 记录当前邻接表的头节点
h[a] = idx; // 更新a的邻接表头指针
}
// 并查集查找操作，路径压缩
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]); // 递归查找根节点并进行路径压缩
return p[x]; // 返回节点x的根节点
}
// Kruskal算法求解最大生成树
void kruskal()
{
sort(edges + 1, edges + cnt + 1); // 按边权从大到小排序
for(int i = 1; i <= n; i++) p[i] = i; // 初始化并查集，初始时每个节点为一个集合
for(int i = 1; i <= cnt; i++)
{
int a = find(edges[i].u); // 找到边的两个端点的根节点
int b = find(edges[i].v);
if(a != b) // 如果两个节点不属于同一集合
{
p[a] = b; // 合并两个集合
edges[i].intree = true; // 标记该边加入到生成树中
}
}
}
// 根据Kruskal算法生成的生成树构建邻接表
void build()
{
memset(h, -1, sizeof(h)); // 初始化邻接表，-1表示没有邻接边
for(int i = 1; i <= cnt; i++) // 遍历所有边
{
if(edges[i].intree) // 只考虑在生成树中的边
{
int a = edges[i].u, b = edges[i].v, c = edges[i].w;
add(a, b, c); // 添加边a->b
add(b, a, c); // 添加边b->a（无向图）
}
}
}
// 深度优先搜索（DFS），计算节点的深度、父节点以及最小边
void dfs(int u, int parent, int dep, int len)
{
depth[u] = dep; // 当前节点的深度
fa[u][0] = parent; // 当前节点的父节点
d[u][0] = len; // 当前边的权重（最小边）
for(int i = 1; i <= 13; i++) // 处理每个节点的2^i父节点和最小边
{
d[u][i] = min(d[u][i - 1], d[fa[u][i - 1]][i - 1]); // 更新节点u到2^i父节点路径上的最小边
fa[u][i] = fa[fa[u][i - 1]][i - 1]; // 更新2^i父节点
}
for(int i = h[u]; ~i; i = ne[i]) // 遍历u的所有邻接边
{
int v = e[i];
if(v == parent) continue; // 如果是父节点，跳过
dfs(v, u, dep + 1, w[i]); // 递归深度优先搜索，深度加1，边权为当前边的权重
}
}
// 求解两个节点的最近公共祖先（LCA），并返回路径上的最小边权
int lca(int u, int v)
{
int res = INF; // 初始化最小边为无穷大
if(depth[u] < depth[v]) swap(u, v); // 保证u的深度大于等于v
for(int i = 13; i >= 0; i--) // 从高到低遍历2^i父节点
{
if(fa[u][i] != -1 && depth[fa[u][i]] >= depth[v]) // 如果u的2^i父节点深度不小于v的深度
{
res = min(res, d[u][i]); // 更新最小边权
u = fa[u][i]; // u跳到2^i父节点
}
}
if(u == v) return res; // 如果u和v已经相同，返回当前的最小边权
for(int i = 13; i >= 0; i--) // 遍历2^i父节点
{
if(fa[u][i] != fa[v][i]) // 如果u和v的2^i父节点不同
{
res = min(res, min(d[u][i], d[v][i])); // 更新最小边权
u = fa[u][i]; // u跳到2^i父节点
v = fa[v][i]; // v跳到2^i父节点
}
}
res = min(res, min(d[u][0], d[v][0])); // 最后检查u和v的父节点
return res; // 返回最小边权
}
int main()
{
cin >> n >> m; // 输入节点数n和边数m
for(int i = 1; i <= m; i++) // 输入所有边
{
cnt++;
cin >> edges[cnt].u >> edges[cnt].v >> edges[cnt].w;
}
// 加入虚拟0点与各个点的边，虚拟点与其他节点的权重为-1
for(int i = 1; i <= n; i++)
{
cnt++;
edges[cnt].u = 0;
edges[cnt].v = i;
edges[cnt].w = -1; // 权重设置为-1，表示虚拟点
}
// 运行Kruskal算法，求解最大生成树
kruskal();
// 构建最大生成树的邻接表
build();
// 初始化深度优先搜索，0作为根节点
dfs(0, -1, 1, INF);
// 处理询问
cin >> q;
while(q--) // 处理q个询问
{
int x, y;
cin >> x >> y;
cout << lca(x, y) << endl; // 输出x和y的LCA路径中的最小边权
}
return 0;
}