题解 P5021 【赛道修建】

tth37 · 2019-07-13 01:13:32 · 题解

题目要求使m条赛道中最短赛道的长度尽可能大，不难想到二分最短赛道的长度len，并判定是否能修建出m条赛道。

定义f[u]为自节点u向下延伸的不作为赛道的最长链长度。假设已知所有的f[v]+w(u,v) (v\in son(u))（即自节点u向下延伸的所有链的长度），则我们应在保证这些链能组成最多赛道的前提下，使保留下来的f[v]+w(u,v)最大。

考虑贪心。对于f[v]+w(u,v)\ge len的情况，可以直接将其作为一条赛道。而剩余的链，只能将它们两两拼接成赛道。由于需要使保留下来的f[v]+w(u,v)取最大值，所以我们可以优先使较短的链得到匹配，在剩余的无法匹配的链中取最值作为新的f[u]。

贪心操作可以用multiset实现。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
struct Edge {int v, w;};
vector<Edge> G[MAXN];
int N, M, L, cnt;
int f[MAXN];
inline bool cmp(int a, int b) {return a > b;}
inline void dfs(int u, int fa) {
    multiset<int> s;
    for (vector<Edge>::iterator it = G[u].begin(); it != G[u].end(); it++) {
        int v = it -> v, w = it -> w;
        if (v == fa) continue;
        dfs(v, u);
        if (f[v] + w >= L) cnt++;
        else s.insert(f[v] + w);
    }
    while (!s.empty()) {
        multiset<int>::iterator it = s.begin();
        s.erase(it);
        multiset<int>::iterator it1 = s.lower_bound(L - *it);
        if (it1 == s.end())
            f[u] = max(f[u], *it);
        else {
            cnt++;
            s.erase(it1);
        }
    }
}
inline bool check() {
    memset(f, 0, sizeof(f));
    cnt = 0;
    dfs(1, 0);
    if (cnt >= M) return 1;
    return 0;
}
int main() {
    scanf("%d%d", &N, &M);
    for (register int i = 1; i < N; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back((Edge){v, w});
        G[v].push_back((Edge){u, w});
    }
    int l = 0, r = 500000000;
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        L = mid;
        if (check()) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    printf("%d", ans);
    return 0;
}