（NOIP2018提高组）洛谷P5021：二分与贪心结合完美解决赛道修建问题

2周前 (09-28)比赛题解90

一、问题理解与建模

洛谷P5021赛道修建问题是一个典型的树形结构上的优化问题。我们需要在给定的树结构道路网络中修建m条赛道，每条赛道由若干条不重复的道路组成，目标是使所有赛道中最短的那条尽可能长。

这个问题可以抽象为：

1.给定一棵n个节点的树，每条边有长度

2.需要选择m条路径（赛道）

3.路径之间不能有重叠的边

4.最大化这m条路径中的最小长度

二、解题思路分析

1.二分答案框架

这类"最小化最大值"或"最大化最小值"的问题通常可以使用‌二分答案‌的方法来解决。具体思路是：

确定答案的可能范围：最小可能值是0，最大可能值是所有边长度之和

对于给定的中间值mid，检查是否能修建至少m条长度≥mid的赛道

根据检查结果调整二分区间

2.贪心验证算法

关键在于如何高效验证对于给定的mid，是否能修建至少m条赛道。这里采用‌贪心算法‌：

从叶子节点开始向上处理

对于每个节点，收集所有子节点传递上来的路径

尽可能多地配对路径，使配对后的路径长度≥mid

无法配对的路径中选择最长的上传给父节点

三、完整代码

#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;

// 二分检查函数
int DFS(int u, int fa, int mid) {
    multiset<int> s;
    for (auto &edge : tree[u]) {
        int v = edge.first, w = edge.second;
        if (v == fa) continue;
        int val = dfs(v, u, mid) + w;
        if (val >= mid) cnt++;
        else s.insert(val);
    }
    
    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;
    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;
}