曾子愚 's Blog

NOIP2013D1T3火车运输最小生成树与LCA优化

第一步：初步分析题目

拿到 P1967「货车运输」这道题，首先要仔细阅读题目描述。

  • 输入：一个图，n 个点，m 条边，每条边有 x, y, z，表示 x 和 y 之间有一条限重为 z 的路。然后是 q 次询问，每次询问两个点 x, y。
  • 目标：对于每次询问 (x, y)，需要找到一条从 x 到 y 的路径，使得这条路径上所有道路的限重中的最小值尽可能大。输出这个最大的最小值。如果 x 和 y 不连通，输出 -1。
  • 例子：从 1 到 3，有两条路径：1-2-3 (限重分别是 4, 3)，这条路径的瓶颈是 min(4, 3) = 3。另一条是 1-3 (限重 1)，瓶颈是 1。为了让瓶颈尽可能大，我们选择第一条路，所以答案是 3。
  • 数据范围：n 和 q 是 10^4 级别，m 是 5 \times 10^4 级别。这意味着对于每次询问，我们不能用像 DFS/BFS 这样 O(N+M) 的复杂度去遍历图，总复杂度会达到 O(q \times (N+M))，肯定会超时。我们需要一个更高效的查询方法。

第二步：转化问题核心

问题的核心是“最大化路径上的最小限重”。这是一个典型的“瓶颈路问题”（Bottleneck Path Problem）。

我希望路径上的所有边限重都尽可能大。这意味着，在选择走哪条路时，我应该优先选择那些限重大的路。如果我有一条限重 100 的路和一条限重 10 的路，我肯定更愿意走那条 100 的。

这启发我，对我来说，图上那些限重小的边是“坏”的，限重大的边是“好”的。为了让任意两点间的通行能力尽可能强，我应该用那些最好的边把所有城市连接起来。

这听起来非常像最小生成树（Minimum Spanning Tree, MST），但反过来了。MST 是为了让总权值最小。这里，我是为了让路径的瓶颈最大。这不就是**最大生成树（Maximum Spanning Tree）**吗？

为什么是最大生成树？

  1. 连通性：我们首先要保证城市之间能互相到达。一个生成树能用最少的边（n-1 条）连接所有 n 个城市。
  2. 最优性：在所有能够连接 u 和 v 的路径中，最大生成树上 u 到 v 的那条唯一路径，恰好就是瓶颈最大的那条路径。
    • 简单证明一下：假设在最大生成树中，u 到 v 的路径 P 上的最小权值为 w。现在假设存在另一条不在树上的路径 P'，其瓶颈 w' 大于 w。路径 P' 中必然至少有一条边 e 不在生成树上。把 e 加入生成树，会形成一个环。这个环上，除了 e 之外的所有边原来都在树上。因为 w' > w，所以边 e 的权值也大于 w。而 u-v 路径 P 上的某条瓶颈边（权值为 w）也一定在这个环上。根据 Kruskal 算法（按权值从大到小加边），我们当初构建最大生成树时，一定会优先考虑 e。如果加入 e 不会形成环，我们就会加入它。但现在 e 和 P 上的边形成了环，说明当初在考虑 e 之前，环上其他边已经被加入了。可是 e 的权值比 P 上的瓶颈边 w 要大，这与 Kruskal 的“从大到小”原则矛盾。因此，不存在瓶颈更大的路径 P'。

结论：这个问题的查询，可以被转化成：先对原图构建一棵最大生成树，然后对于每次查询 (x, y)，找出树上从 x 到 y 的唯一路径，并求这条路径上边权的最小值。

第三步：解决转化后的问题

好了，现在问题变成了“查询树上两点路径的边权最小值”。

  • 构建最大生成树：用 Kruskal 算法。将所有边按权值 z 从大到小排序。依次遍历边，如果一条边的两个端点不在同一个连通块里（用并查集判断），就将这条边加入生成树，并合并两个连通块。这正是我的代码里用优先队列（大顶堆）实现的部分。

    // 按照 z 从大到小排序
std::priority_queue<XYZ> pq; 
...
// Kruskal 过程
while(pq.size() && mergednum < n-1){
    auto[x,y,z] = pq.top();
    pq.pop();
    if(ismerged(x, y))continue; // 并查集判断环
    edg[x].emplace_back(y,z);   // 加入新图（生成树）
    edg[y].emplace_back(x,z);
    merge(x, y);                // 合并
    mergednum++;
}

  • 查询路径最小值：对于每次查询 (x, y)，需要在树上找到路径并求最小值。

    • 暴力方法：从 x 开始 DFS/BFS 到 y，记录途中最小边权。如前所述，q 次查询太慢。
    • 高效方法：我们需要快速查询。树上两点路径问题，自然想到最近公共祖先（LCA）。
    • 路径 x -> y 可以被拆分成两段：x -> LCA(x, y) 和 y -> LCA(x, y)。
    • 问题就变成了求 x 到其祖先 LCA(x, y) 路径上的最小值，和 y 到其祖先 LCA(x, y) 路径上的最小值，然后在这两个值中再取一个较小值。

第四步：实现 LCA 和路径查询的优化

如何快速求 LCA 和路径最小值？**倍增（Binary Lifting）**是经典方法。

我需要预处理两个数组：

  1. fth[i][j]：节点 i 的第 2^j 个祖先。
  2. cost[i][j]：节点 i 到其第 2^j 个祖先的路径上，边权的最小值。

  • 预处理 (DFS)：

    • 首先通过一次 DFS 遍历整棵树，确定每个节点的深度 dpth 和它的直接父亲 fth[i][0]。
    • 同时，cost[i][0] 就是 i 和它父亲 fth[i][0] 之间边的权值。
    • 然后进行倍增递推：
      • fth[i][j] = fth[ fth[i][j-1] ][j-1]
        （我跳 2^j 步，等于先跳 2^{j-1} 步，再从落点跳 2^{j-1} 步）
      • cost[i][j] = min( cost[i][j-1], cost[ fth[i][j-1] ][j-1] )
        （从 i 到第 2^j 祖先路径上的最小值，等于 i 到第 2^{j-1} 祖先的最小值 和 第 2^{j-1} 祖先到第 2^j 祖先的最小值的 min）
    • 这部分逻辑在我的 dfs 函数中实现。

  • 查询 (LCA)：

    1. 让 x 和 y 中深度较大的那个点（假设是 y）向上跳，直到和 x 同一深度。在向上跳的过程中，把经过的路径的 cost 值累积起来求 min。 
      // ll tmp = dpth[b]-dpth[1],ans=0;错误 // 思考过程中的小错误，深度应该和另一个点对齐
ll tmp = dpth[b]-dpth[a],ans=inf;
for(ll j=0;tmp;j++,tmp>>=1){
    if(tmp&1){
        ans=std::min(ans,cost[b][j]);
        b=fth[b][j];
    }
}
    2. 如果此时 x 和 y 相遇，说明一个是另一个的祖先，路径最小值已经求出，直接返回 ans。
    3. 如果没相遇，就让 x 和 y 一起向上跳，直到它们的父节点相同。同样，在跳跃过程中，累积 cost 的最小值。 
      for(ll j=maxlog;j>=0 && a!=b;j--){
    if(fth[a][j]!=fth[b][j]){
        ans=std::min({ans,cost[a][j],cost[b][j]});
        a=fth[a][j];
        b=fth[b][j];
    }
}
    4. 最后，x 和 y 的父节点就是 LCA。别忘了，还有从 x, y 到它们共同父节点的最后两条边。 
      ans=std::min({ans,cost[a][0],cost[b][0]});

第五步：处理边界和细节

  • 不连通：如果一开始两个城市就不在同一个连通分量里，那么在最大生成树里它们也肯定不连通。Kruskal 算法结束后，并查集里 find(x) != find(y) 就意味着不连通。所以查询时先判断一下即可。

    if (!ismerged(a, b)) {
    std::cout<<"-1\n";
    continue;
}

  • 森林：原图可能不连通，形成一个森林。我的代码中用 if(dpth[i]==0) 来确保对每个连通分量（每棵树）都执行 DFS 预处理，这是很完备的。

  • 重边：题目说“两座城市之间可能有多条道路”。Kruskal 算法天生就能处理重边。因为它按权值从大到小处理，对于两个城市间的 多条道路，它会首先考虑权值最大的那条。一旦连接，其他权值较小的边在后续都会因为形成环而被忽略。

到这里，整个解题思路就非常清晰了：最大生成树 + LCA + 倍增优化。我的代码完全遵循了这个思路。现在，可以开始写文章了。

题解：从货车运输问题看最大生成树与LCA倍增优化

你好，旅行者！欢迎来到这篇题解。在这里，我将带你一步步拆解 NOIP 2013 的经典题目「货车运输」，并模拟我的完整思考过程。我们将从理解问题本质出发，引出核心算法，最终通过代码实现来解决它。

Part 1: 算法讲解 - 我们的工具箱

在解决具体问题之前，我们先来准备两件强大的工具：最大生成树和带倍增优化的LCA。

1. 问题的本质与最大生成树（Maximum Spanning Tree）

这道题要求我们找到一条路径，使得路径上边权的最小值尽可能大。这是一个经典的“瓶颈最大化”问题。

思考过程：

  • 为了让路径的“瓶颈”（即最小限重）尽可能大，我们应当优先使用那些限重大的道路。
  • 如果我们想让整个交通网络中的任意两点之间的通行能力都尽可能强，我们应该用那些权值最高的边来构建网络的骨架。
  • 这个“骨架”需要连接所有城市，并且总的“质量”最好。这让我们联想到了最小生成树（MST）。但 MST 是让总权值之和最小，而我们是想让瓶颈权值最大。所以，我们需要的恰恰是它的对偶问题——最大生成树 (Maximum Spanning Tree)。

什么是最大生成树？
在一个带权无向图中，连接所有顶点且边权之和最大的树。

为什么是它？
最大生成树有一个非常重要的性质：对于树中任意两个节点 u 和 v，它们之间的唯一路径，就是原图中所有 u 到 v 的路径里，瓶颈（路径最小边权）最大的那一条。

如何构建？
我们可以使用 Kruskal 算法 的变体。标准的 Kruskal 是将边按权值从小到大排序，而构建最大生成树时，我们只需将边从大到小排序，然后依次尝试加入。使用**并查集（Union-Find）**来判断新加入的边是否会形成环即可。这正是我的代码中使用大顶堆 priority_queue 和 unf 数组（并查集）所做的事情。

// 优先队列默认是大顶堆，正好满足我们从大到小处理边的需求
std::priority_queue<XYZ> pq;
// ... 读入所有边并放入pq ...

// Kruskal算法构建最大生成树
while(pq.size() && mergednum < n-1){
    auto[x,y,z] = pq.top(); // 取出当前限重最大的边
    pq.pop();
    if(ismerged(x, y)) continue; // 如果已连通，则会形成环，跳过
    // 将这条优质边加入我们的生成树
    edg[x].emplace_back(y,z);
    edg[y].emplace_back(x,z);
    merge(x, y); // 合并两个集合
    mergednum++;
}

2. 树上查询与 LCA + 倍增优化

通过第一步，我们把问题从一个复杂的图问题，简化为了一个树上问题：对于每次查询 (u, v)，求树上 u 到 v 唯一路径的最小边权。

思考过程：

  • 直接查询？ 每次查询都从 u DFS 到 v？Q 次查询，每次 O(N)，总复杂度 O(QN)，对于 10^4 的数据量来说太慢了。
  • 路径拆分：树上两点 u, v 的路径可以被它们的最近公共祖先 (LCA, Lowest Common Ancestor) 分为两段：u -> LCA(u,v) 和 v -> LCA(u,v)。问题就变成了求这两段路径上的边权最小值。
  • 快速查询：如何快速求一个节点到它某个祖先路径上的信息？这就是**倍增（Binary Lifting）**的用武之地。

倍增如何工作？

我们通过一次 dfs 预处理出两个关键数组：

  1. fth[i][j]：节点 i 的第 2^j 个祖先。
  2. cost[i][j]：节点 i 到它的第 2^j 个祖先的路径上，所有边权的最小值。

这两个数组可以通过递推得到：

  • Base Case: fth[i][0] 是 i 的父亲，cost[i][0] 是 (i, fth[i][0]) 这条边的权值。
  • 递推关系:
    • fth[i][j] = fth[ fth[i][j-1] ][j-1] (我跳 2^j 步 = 先跳 2^{j-1} 步，再从落点跳 2^{j-1} 步)
    • cost[i][j] = min( cost[i][j-1], cost[ fth[i][j-1] ][j-1] ) (从i到第 2^j 祖先的瓶颈 = 前半段路程的瓶颈 vs 后半段路程的瓶颈)

我的 dfs 函数正是用来完成这个预处理的：

static inline void dfs(ll f,ll cur){
    dpth[cur]=dpth[f]+1;
    fth[cur][0]=f; // Base Case: 2^0 祖先是父亲
    for(ll i=1;i<=maxlog;i++){ // 递推
        fth[cur][i]=fth[fth[cur][i-1]][i-1];
        cost[cur][i]=std::min(cost[fth[cur][i-1]][i-1],cost[cur][i-1]);
    }
    for(auto nxt:edg[cur]){ // 遍历子节点
        if(nxt.to==f)continue;
        cost[nxt.to][0]=nxt.w; // 初始化子节点的 cost Base Case
        dfs(cur,nxt.to);
    }
}

有了这两个数组，我们就可以在 O(\log N) 的时间内完成一次查询。

Part 2: 题解 - 串联算法，解决问题

现在，让我们把工具箱里的工具组合起来，完整地解决「货车运输」问题。

解题总纲：

  1. 转化：将问题理解为在原图上寻找瓶颈最大的路径。
  2. 建模：通过构建最大生成树，将问题简化为查询树上两点路径的最小边权。
  3. 求解：利用LCA+倍增的思想，预处理信息，实现对路径最小值的快速查询。

详细步骤与代码剖析

1. 建立最大生成树

如前文所述，我们使用 Kruskal 算法和并查集。代码中的 priority_queue 充当了排序的角色，每次取出权值最大的边。并查集 unf、find、merge 用来维护连通性。

关键点：main函数中的这个循环构建了我们的“最优运输网络”。

// main 函数中
while(pq.size() && mergednum < n-1){
    auto[x,y,z] = pq.top();
    pq.pop();
    if(ismerged(x, y))continue;
    edg[x].emplace_back(y,z);
    edg[y].emplace_back(x,z);
    merge(x, y);
    mergednum++;
}

注意：在Kruskal的过程中，我们只保留了构成最大生成树的边，存入了新的邻接表 edg 中。后续所有操作都在这张新图（树）上进行。

2. 预处理 (DFS)

建好树后，我们需要对它进行一次深度优先搜索（DFS），来填充我们的 fth 和 cost 倍增数组。

// main 函数中
// 循环是为了处理原图不连通，形成森林的情况
for(ll i=1;i<=n;i++){
    if(dpth[i]==0){ // 如果这个点还没被访问过（属于一棵新树）
        dpth[0]=0;  // 虚拟根节点0的深度为0
        dfs(0,i);   // 从这个点开始DFS
    }
}

dfs 函数的具体实现已在上一节展示，它为我们后续的快速查询奠定了基础。

3. 处理查询

这是最核心的部分，由 lca 函数实现，它同时完成了求LCA和路径瓶颈两个任务。

static inline ll lca(ll a,ll b){
    // 1. 将 a, b 移动到同一深度
    if(dpth[a]>dpth[b])std::swap(a,b);
    ll tmp = dpth[b]-dpth[a], ans=inf;
    for(ll j=0;tmp;j++,tmp>>=1){
        if(tmp&1){ // 二进制拆分，每次跳2^j步
            ans=std::min(ans,cost[b][j]); // 记录路径上的瓶颈
            b=fth[b][j];
        }
    }
  
    // 如果此时 a,b 相遇，说明 a 是 b 的祖先，路径瓶颈已找到
    if(a==b)return ans;

    // 2. a, b 一起向上跳，直到它们的父节点相同
    for(ll j=maxlog;j>=0; j--){
        if(fth[a][j]!=fth[b][j]){
            ans=std::min({ans,cost[a][j],cost[b][j]}); // 同时记录两边路径的瓶颈
            a=fth[a][j];
            b=fth[b][j];
        }
    }
  
    // 3. 最后一步，a和b的父节点就是LCA，记录最后两条边的权值
    ans=std::min({ans,cost[a][0],cost[b][0]});
    return ans;
}

在主函数的查询循环中，我们调用它：

// main 函数中
std::cin>>q;
for(ll i=1;i<=q;i++){
    ll a,b;
    std::cin>>a>>b;
    // 特判：如果两点在原图中就不连通
    if (!ismerged(a, b)) { // 并查集的状态保留了最终的连通性
        std::cout<<"-1\n";
        continue;
    }
    std::cout<<lca(a,b)<<'\n'; // 输出查询结果
}

一个重要的细节：ismerged(a,b) 判断不连通。在Kruskal建树结束后，并查集 unf 记录了最终的连通分量信息。如果两个点在此时 find 的结果都不同，说明它们在原图中也无法互相到达。

总结

回顾整个过程，我们完成了一次漂亮的思维转换：

  1. 原始问题：在任意图中，找一条路径，使其最小边权最大。
  2. 转化为：在最大生成树上，找两点间的唯一路径，并求该路径上的最小边权。
  3. 再转化为：利用LCA + 倍增，将问题拆解为 u -> lca 和 v -> lca 两段，并在 O(\log N) 时间内查询路径最小值。

这个解法巧妙地结合了图论中的经典算法，将一个看似复杂的查询问题，通过预处理和数据结构的优化，变得高效而优雅。希望这次模拟思考能帮助你更深入地理解这些算法的应用场景！

Zengtudor

© 2025 曾子愚 's Blog