题目分析

本题要求计算货车在两个城市之间运输时能承受的最大重量，即找到从起点到终点路径上的最小限重最大值。

---

问题抽象

给定一个无向图 $G=(V,E)$，每条边有权重 $w$（限重）。
对于每个查询 $(x,y)$，求从 $x$ 到 $y$ 的所有路径中，路径上最小边权的最大值。
即求：

$$\max_{P \in \text{Paths}(x,y)} \min_{e \in P} w(e) $$

如果 $x$ 和 $y$ 不连通，输出 $-1$。

---

算法思路

1. 最大生成树性质

根据图论知识，任意两点间最小边权最大的路径一定在图的最大生成树上。
因此可以先用 Kruskal 算法求出最大生成树。

2. 树上的路径查询

在最大生成树上，$x$ 到 $y$ 路径上的最小边权就是答案。
这可以通过预处理树的 LCA（最近公共祖先）来快速计算。

---

代码解析

数据结构定义

const int N = 10005, M = 50005;
struct node {
    int a, b, w;
} f[M];  // 存储所有边
vector<edge> e[N];  // 最大生成树的邻接表
int F[N], V[N], fa[N], dep[N], color[N];  // 树相关数组

1. Kruskal算法构建最大生成树

void Kruskal() {
    sort(f + 1, f + 1 + m, cmp);  // 按边权降序排序
    
    for (int i = 1; i <= n; i++)
        fa[i] = i;  // 初始化并查集
        
    for (int i = 1; i <= m; i++) {
        int x = f[i].a, y = f[i].b, w = f[i].w;
        int fx = find(x), fy = find(y);
        
        if (fx == fy) continue;  // 已连通则跳过
        
        fa[fx] = fy;  // 合并
        e[x].push_back({y, w});  // 添加树边
        e[y].push_back({x, w});
    }
}

2. 树的DFS预处理

void Paint(int x, int fax) {
    color[x] = cnt;    // 标记连通分量
    F[x] = fax;        // 记录父节点
    dep[x] = dep[fax] + 1;  // 记录深度
    
    for (auto edge : e[x]) {
        int y = edge.id, w = edge.w;
        if (y == fax) continue;
        
        V[y] = w;      // 记录到父节点边的权值
        Paint(y, x);   // 递归遍历
    }
}

3. LCA查询路径最小边权

int LCA(int x, int y) {
    if (color[x] != color[y]) return -1;  // 不连通
    
    int ans = 0x3f3f3f3f;
    
    // 先将深度较深的节点向上提升
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) {
        ans = min(ans, V[x]);  // 记录路径上的最小边权
        x = F[x];
    }
    
    if (x == y) return ans;  // 重合情况
    
    // 同时向上提升直到相遇
    while (x != y) {
        ans = min(ans, min(V[x], V[y]));
        x = F[x], y = F[y];
    }
    
    return ans;
}

---

算法流程

1. 输入处理：读入城市数 $n$、道路数 $m$ 和所有道路信息
2. 构建最大生成树：使用 Kruskal 算法
3. 预处理树结构：对每个连通分量进行 DFS，记录父节点、深度和边权
4. 处理查询：对于每个查询 $(x,y)$，用 LCA 方法求路径最小边权
5. 输出结果：根据连通性输出答案或 $-1$

---

复杂度分析

• 时间复杂度：

  • Kruskal 算法：$O(m \log m)$
  • 树的 DFS：$O(n)$
  • 每个查询：$O(\log n)$
  • 总复杂度：$O(m \log m + n + q \log n)$

• 空间复杂度：$O(n + m)$

---

示例验证

样例输入：

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

处理过程：

1. 最大生成树包含边 $(1,2,4)$ 和 $(2,3,3)$
2. 查询 $(1,3)$：路径 $1 \to 2 \to 3$，最小边权为 $\min(4,3)=3$
3. 查询 $(1,4)$：$1$ 和 $4$ 不连通，输出 $-1$
4. 查询 $(1,3)$：同上，输出 $3$

输出：

3
-1
3

与题目样例完全一致。

---

关键点总结

• 利用最大生成树的性质简化问题
• 通过LCA快速查询树上路径信息
• 使用并查集维护连通性和构建生成树
• 注意处理多连通分量的情况