当前位置：首页 > 提高组 > （2018年NOIP提高组）洛谷P5021题：二分查找+动态规划解决赛道修建

（2018年NOIP提高组）洛谷P5021题：二分查找+动态规划解决赛道修建

2个月前 (08-20)

一、题目解读

洛谷P5021题（2018年NOIP提高组）要求在一棵带权树中，查找满足路径权重大于等于指定阈值的最小阈值，同时保证符合条件的路径数量达到给定目标。问题本质是图论中的路径计数与二分查找的结合，需通过动态规划思想优化求解过程。

二、解题思路

采用二分查找阈值，将问题转化为“检查是否存在至少m条路径权重大于等于mid”。核心逻辑为：

1. 通过DFS遍历树，递归计算子树中以各节点为起点的最大路径权重；

2. 利用multiset存储未达标路径，通过二分匹配查找互补路径对，统计满足条件的路径数；

3. 动态调整阈值区间，直至找到符合条件的最小阈值。

三、解题步骤

1. 建图与数据预处理：用vector存储树边信息，记录每条边的权重，初始化左右边界（路径权重范围）；

2. 二分查找阈值：通过mid = (left + right) / 2迭代，调用DFS检查路径数量；

3. DFS递归计算：

○ 遍历当前节点的子树，递归获取子节点的最大路径权值（含边权）；

○ 若子路径≥mid则计入cnt，否则存入multiset；

○ 通过multiset动态匹配路径对，更新cnt并维护最长单路径；

4. 阈值判定与收敛：若cnt≥m则左移区间（缩小阈值），反之右移，最终获取最小合法阈值。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
#include<set>
using namespace std;

const int MAXN = 50010;
vector<pair<int, int>> tree[MAXN]; // 存储树边：节点-邻接点, 权重
int n, m, cnt; // n:节点数, m:目标路径数, cnt:当前合法路径计数

// 二分检查函数
int dfs(int u, int fa, int mid) { // u:当前节点, fa:父节点, mid:阈值
    multiset<int> s; // 存储未达标路径
    for (auto &edge : tree[u]) { // 遍历子树
        int v = edge.first, w = edge.second; // 邻接点v, 边权w
        if (v == fa) continue; // 跳过父节点
        int val = dfs(v, u, mid) + w; // 递归获取子树最大路径 + 边权
        if (val >= mid) cnt++; // 若≥阈值则计数
        else s.insert(val); // 否则存入multiset
    }
    
    int max_path = 0; // 记录当前节点最长单路径
    while (!s.empty()) { // 动态匹配路径对
        auto it = s.begin(); // 取最小未达标路径
        int x = *it;
        s.erase(it);
        auto match = s.lower_bound(mid - x); // 查找互补路径
        if (match!= s.end()) { // 若存在匹配
            cnt++; // 计数
            s.erase(match); // 删除配对路径
        } else { // 无匹配则更新最长单路径
            max_path = max(max_path, x);
        }
    }
    return max_path; // 返回当前节点最长单路径（用于后续递归）
}

int main() {
    cin >> n >> m; // 输入节点数n, 目标路径数m
    int left = 0, right = 0; // 初始化阈值区间
    for (int i = 1; i < n; i++) { // 建图
        int a, b, l;
        cin >> a >> b >> l; // 输入边信息
        tree[a].emplace_back(b, l); // 双向边
        tree[b].emplace_back(a, l);
        right += l; // 更新右边界（最大路径权）
    }
    
    int ans = 0; // 最终答案
    while (left <= right) { // 二分查找
        int mid = (left + right) / 2;
        cnt = 0; // 重置计数
        dfs(1, 0, mid); // 从根节点开始检查
        if (cnt >= m) { // 若路径数达标
            ans = mid; // 记录答案
            left = mid + 1; // 左移区间（缩小阈值）
        } else {
            right = mid - 1; // 右移区间（增大阈值）
        }
    }
    cout << ans << endl; // 输出结果
    return 0;
}