NOIP2018提高组 T3 题解

关于使用AI

1. 代码由我书写，注释和解释由ai书写
2. 文章经过了我的审核

问题描述

C 城即将举办一系列赛车比赛。比赛前需要在城内修建 m 条赛道。城内有 n 个路口，编号为 1, 2, \dots, n，这些路口通过 n-1 条双向道路相连，形成一棵树结构。每条道路连接两个路口，并有一个长度 l_i。

赛道的定义与要求如下：

• 每条赛道是一组互不相同的道路，形成一条从某个路口出发，经过一系列道路到达另一个路口的路径。
• 每条道路在所有赛道中至多被一条赛道使用（即赛道之间不允许有道路重叠）。
• 赛道的长度为其包含的所有道路长度之和。

目标：
设计一种赛道修建方案，使得在修建的 m 条赛道中，长度最小的赛道的长度尽可能大。

简而言之，我们需要从树中选择 m 条互不重叠的路径，使得这些路径中的最短路径尽可能长。

算法思路

为了找到满足条件的最大最小赛道长度，我们可以使用二分查找结合深度优先搜索（DFS） 的方法来解决问题。

步骤如下：

1. 二分查找范围确定：

   • 最小长度 L 为所有道路的最小长度。
   • 最大长度 R 为所有道路长度之和。

2. 中点尝试：

   • 取中点 mid = (L + R) / 2，尝试判断是否可以构造出至少 m 条路径，每条路径的长度都至少为 mid。

3. DFS 检查：

   • 从树的根节点开始进行 DFS。
   • 在每个节点，尝试向下枚举可能的路径长度，并统计可以形成满足条件的赛道数。
   • 利用贪心策略尽可能组合子路径，尝试达到或超过 mid。

4. 更新二分查找范围：

   • 如果可以构造出至少 m 条满足条件的赛道，则尝试增大 mid（即 L = mid + 1）。
   • 否则，减小 mid（即 R = mid - 1）。

5. 最终答案：

   • 当二分查找结束时，R 即为所求的最大最小赛道长度。

代码详解与注释

以下是经过详细注释的代码版本，结合了上述算法思路进行解释。

#include <bits/stdc++.h>

using ll = int64_t; // 定义长整型
using std::cin, std::cout;

// 常量定义
const ll maxn = 5e4 + 5;           // 最大节点数
const ll inf = (ll(1) << 60);      // 无穷大，用于初始最小值

ll n, m;                           // 节点数和赛道数
ll mins = inf;                     // 道路的最小长度初始化为无穷大
ll maxs = 0;                       // 道路总长度初始化为0
ll g[maxn], f[maxn];               // g[u]：当前节点u向上传递的最长路径长度
                                    // f[u]：当前节点u子树中形成的赛道数
std::vector<std::pair<ll, ll>> adj[maxn]; // 邻接表存储树结构，pair形式为（邻接节点, 道路长度）

/**
 * @brief 深度优先搜索，用于计算在给定的最小赛道长度num下，可以形成多少条满足条件的赛道。
 * @param fth 当前节点的父节点
 * @param u 当前访问的节点
 * @param num 当前尝试的最小赛道长度
 */
void dfs(ll fth, ll u, const ll& num){
    std::multiset<ll> ms; // 存储当前节点所有子路径的部分长度

    // 遍历当前节点的所有邻接节点
    for(auto [v, w] : adj[u]){
        if(fth == v) continue; // 避免回到父节点

        dfs(u, v, num);       // 递归遍历子节点
        f[u] += f[v];         // 累加子节点已经形成的赛道数

        ll ff = g[v] + w;     // 计算从子节点v向上传递的路径长度
        if(ff >= num){
            ++f[u];            // 该路径长度已满足至少为num，可以形成一条赛道
        }
        else{
            ms.emplace(ff);    // 不足，则记录下来，尝试与其他路径组合
        }
    }

    // 如果没有残余的部分路径，不需要处理
    if(ms.empty()) return;

    if(ms.size() == 1){
        // 只有一个残余路径，无法与其他路径组合，直接传递
        g[u] = *ms.begin();
        return;
    }

    ll ans = -1; // 记录无法组合的路径长度
    ll nans;

    while(ms.size() >= 2){
        nans = *ms.begin();      // 取出最小的部分路径
        ms.erase(ms.begin());    // 移除该部分

        // 尝试在剩余的部分路径中找到一个，使得两者之和 >= num
        // 即寻找 >= (num - nans) 的最小值
        auto fit = ms.lower_bound(num - nans);
        if(fit == ms.end()){
            // 没有找到满足条件的路径，记录当前的nans
            ans = nans;
        }
        else{
            // 找到了一个可以与nans组合形成一条赛道
            f[u]++;                 // 增加一个赛道
            ms.erase(fit);          // 移除该路径，避免重用
        }
    }

    // 处理剩余的一个路径
    if(ms.size() > 0){
        g[u] = *std::prev(ms.end()); // 传递最大的剩余路径
    }
    else if(ans != -1){
        g[u] = ans; // 传递无法组合的路径
    }
}

/**
 * @brief 检查在最小赛道长度为num的情况下，是否可以形成至少m条赛道。
 * @param num 当前尝试的最小赛道长度
 * @return 如果可以形成至少m条赛道，则返回true；否则返回false
 */
bool check(ll num){
    std::fill(f, f + 1 + n, 0); // 初始化赛道计数
    std::fill(g, g + 1 + n, 0); // 初始化路径长度
    dfs(0, 1, num);              // 从根节点1开始DFS
    return f[1] >= m;             // 判断总赛道数是否满足
}

int main(){
    // 优化输入输出速度
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m; // 读取节点数和赛道数

    // 读取n-1条道路，并构建邻接表
    for(ll i = 1; i < n; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        mins = std::min(mins, w); // 更新道路最小长度
        maxs += w;                 // 计算所有道路的总长度
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    ll l = mins, r = maxs; // 初始化二分查找的左右边界
    ll ans = l;             // 初始答案设为最小道路长度
    ll mid;

    // 二分查找，寻找满足条件的最大最小赛道长度
    while(l <= r){
        mid = (l + r) / 2;
        if(check(mid)){
            ans = mid; // 如果可以满足，尝试更大的mid
            l = mid + 1;
        }
        else{
            r = mid - 1; // 否则，缩小mid
        }
    }

    cout << ans << '\n'; // 输出最终答案
}

代码详解

1. 输入与邻接表构建：

   cin >> n >> m; // 读取节点数和赛道数
   
   // 读取n-1条道路，并构建邻接表
   for(ll i = 1; i < n; i++){
       ll u, v, w;
       cin >> u >> v >> w;
       mins = std::min(mins, w); // 更新道路最小长度
       maxs += w;                 // 计算所有道路的总长度
       adj[u].emplace_back(v, w);
       adj[v].emplace_back(u, w);
   }
   

   这里，我们读取了树的结构，并通过邻接表 adj 存储每个节点的邻接节点及其道路长度。同时，计算了所有道路的最小长度 mins 和总长度 maxs，用于二分查找的初始范围。

2. 二分查找部分：

   ll l = mins, r = maxs; // 初始化二分查找的左右边界
   ll ans = l;             // 初始答案设为最小道路长度
   ll mid;
   
   // 二分查找，寻找满足条件的最大最小赛道长度
   while(l <= r){
       mid = (l + r) / 2;
       if(check(mid)){
           ans = mid; // 如果可以满足，尝试更大的mid
           l = mid + 1;
       }
       else{
           r = mid - 1; // 否则，缩小mid
       }
   }
   
   cout << ans << '\n'; // 输出最终答案
   

   通过二分查找，我们在 mins 和 maxs 之间寻找最大的 mid，使得至少可以形成 m 条长度不小于 mid 的赛道。check(mid) 函数用于判断是否满足条件。

3. 检查函数 check(ll num)：

   bool check(ll num){
       std::fill(f, f + 1 + n, 0); // 初始化赛道计数
       std::fill(g, g + 1 + n, 0); // 初始化路径长度
       dfs(0, 1, num);              // 从根节点1开始DFS
       return f[1] >= m;             // 判断总赛道数是否满足
   }
   

   这个函数通过调用 dfs，计算在给定的最小赛道长度 num 下，能够形成的赛道数。若满足至少 m 条，则返回 true。

4. 深度优先搜索函数 dfs(ll fth, ll u, const ll& num)：

   void dfs(ll fth, ll u, const ll& num){
       std::multiset<ll> ms; // 存储当前节点所有子路径的部分长度
   
       // 遍历当前节点的所有邻接节点
       for(auto [v, w] : adj[u]){
           if(fth == v) continue; // 避免回到父节点
   
           dfs(u, v, num);       // 递归遍历子节点
           f[u] += f[v];         // 累加子节点已经形成的赛道数
   
           ll ff = g[v] + w;     // 计算从子节点v向上传递的路径长度
           if(ff >= num){
               ++f[u];            // 该路径长度已满足至少为num，可以形成一条赛道
           }
           else{
               ms.emplace(ff);    // 不足，则记录下来，尝试与其他路径组合
           }
       }
   
       // 如果没有残余的部分路径，不需要处理
       if(ms.empty()) return;
   
       if(ms.size() == 1){
           // 只有一个残余路径，无法与其他路径组合，直接传递
           g[u] = *ms.begin();
           return;
       }
   
       ll ans = -1; // 记录无法组合的路径长度
       ll nans;
   
       while(ms.size() >= 2){
           nans = *ms.begin();      // 取出最小的部分路径
           ms.erase(ms.begin());    // 移除该部分
   
           // 尝试在剩余的部分路径中找到一个，使得两者之和 >= num
           // 即寻找 >= (num - nans) 的最小值
           auto fit = ms.lower_bound(num - nans);
           if(fit == ms.end()){
               // 没有找到满足条件的路径，记录当前的nans
               ans = nans;
           }
           else{
               // 找到了一个可以与nans组合形成一条赛道
               f[u]++;                 // 增加一个赛道
               ms.erase(fit);          // 移除该路径，避免重用
           }
       }
   
       // 处理剩余的一个路径
       if(ms.size() > 0){
           g[u] = *std::prev(ms.end()); // 传递最大的剩余路径
       }
       else if(ans != -1){
           g[u] = ans; // 传递无法组合的路径
       }
   }
   

   核心逻辑解释：

   • 目的： 在给定最小赛道长度 num 的条件下，统计当前子树能够形成的赛道数。

   • 工作原理：

     1. 对于每个子节点，递归获取其向上传递的最长路径长度 g[v]。
     2. 若 g[v] + w >= num，则可以形成一条赛道，赛道数 f[u] 增加。
     3. 否则，将 g[v] + w 放入多重集合 ms 中，尝试与其他部分路径组合以达到 num。
     4. 通过贪心的方法，尽可能地将最小的部分路径与合适的另一部分路径组合，形成尽量多的赛道。
     5. 最终，未能组合的最大部分路径长度被传递给父节点，供上层继续组合使用。

   • 为什么使用 multiset：
     使用 multiset 是因为我们需要频繁地进行插入、删除、查找操作，并且需要保持有序，以便快速找到能够与当前部分路径组合达到 num 的另一部分路径。

总结

本题的目标是从一棵树中选择 m 条互不重叠的路径，使得这些路径中的最短路径尽可能长。为了高效地找到这个最大最小值，我们采用了二分查找结合深度优先搜索的策略。

关键点总结：

1. 二分查找： 用于在可能的最小赛道长度范围内高效定位目标值。

2. 深度优先搜索（DFS）： 在每次二分查找的尝试中，DFS 用于遍历树并统计符合当前最小赛道长度条件的赛道数。

3. 贪心策略： 在 DFS 中，通过贪心地组合子路径，最大化赛道数，确保路径不重叠且尽可能利用已有的部分路径。

4. 数据结构选择： 使用 multiset 来高效处理部分路径的管理和组合，确保算法的效率和正确性。

通过这种方法，我们能够在较大的数据规模下（如 n \leq 5 \times 10^4）高效地解决问题，满足题目的时间和空间要求。

进一步优化与思考：

• 时间复杂度： 主体部分的时间复杂度取决于二分查找的次数（约 O(\log S)，S 为总长度）以及每次 check 操作的复杂度（线性遍历所有节点和部分集合）。总体上，适用于题目给定的数据规模。

• 空间复杂度： 主要由邻接表和辅助数组 f、g 组成，符合题目限制。

• 可能的优化： 在实现中，可以通过一些技巧减少 multiset 的使用次数，如通过优先队列等更高效的数据结构，进一步提升常数性能。