Luogu5021 赛道修建

发布于 2019-10-29  193 次阅读


Link

题意

给你一棵树,让你选 m 条路。每条路都满足不会往回走(即不重复经过路径上的点)。让你求一种方案,使得修建的 m 条赛道中长度最小的赛道长度最大(即 m 条赛道中最短赛道的长度尽可能大)

题解

看上去有点难,做起来难度适中。

看样例,考虑 m=1 的情况,显然就是让我们在树上选一条最长路和次长路,求和(讲白了就是树的直径)即可。

考虑所有情况,一条满足要求的赛道应该分为两种情况(墙裂建议不要看样例解释的图):

  1. 从深到浅的一条链
  2. 从深到浅再到与原来不同向的深处

再者

使得修建的 m 条赛道中长度最小的赛道长度最大(即 m 条赛道中最短赛道的长度尽可能大)

这不是暗示你二分这条边的长度吗?(屁的暗示就是告诉你要二分)

我们设二分的答案为 Mid

那么我们可以DFS一下,把子节点传上来的链的长度进行分析:

设从子节点传上来的链的长度为 val , 当前节点与该子节点之间的距离为 d

  1. $val + d ≥ Mid$
  2. $val + d < Mid$

对于第一种情况,我们只要用一个计数器统计数量即可。(意为又找到了一条满足要求的赛道)

而对于第二种情况,我们把它丢进一个multiset中维护。

如何处理当前这个可重集中的答案呢?我们可以二分答案集合中与它求和后大于 Mid 的最小边。

这个过程可以直接用lower_bound实现。

之后再从集合中删掉着两条边即可。

详细实现看代码

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 50000 + 5;

int n, m, num, Left, Right, Mid, cnt;
int head[SIZE], dis1[SIZE], dis2[SIZE];

struct node {
    int to, v, Next;
} edge[SIZE << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y, int z)
{
    edge[++num].to = y;
    edge[num].v = z;
    edge[num].Next = head[x];
    head[x] = num;
}

namespace initation {
    void DFS(int u, int fa)
    {
        for (int i = head[u]; i; i = edge[i].Next) {
            int v = edge[i].to;
            if (v == fa) continue;
            DFS(v, u);
            if (dis1[v] + edge[i].v > dis1[u]) dis2[u] = dis1[u], dis1[u] = dis1[v] + edge[i].v;
            else dis2[u] = std::max(dis2[u], dis1[v] + edge[i].v);
        }
    }
}

inline int DFS(int u, int fa)
{
    std::multiset < int > s;
    s.clear();
    for (int i = head[u]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (v == fa) continue;
        int val = DFS(v, u) + edge[i].v;
        if (val >= Mid) cnt++;
        else s.insert(val);
    }
    int sum = 0;
    while (!s.empty()) {
        std::multiset < int >::iterator i = s.begin(), j = s.lower_bound(Mid - *i);
        if (((i == j) && s.count(*i) == 1)) j++;
        if (j == s.end()) {
            sum = std::max(sum, *i);
            s.erase(i);
            continue;
        }
        cnt++;
        s.erase(s.find(*i)), s.erase(s.find(*j));
    }
    return sum;
}

inline int Judge()
{
    cnt = 0;
    DFS(1, 0);
    if (cnt >= m) return 1;
    return 0;
}

signed main()
{
    int u, v, d, ans = 0;
    n = read(), m = read();
    Left = 2e9;
    for (int i = 1; i < n; i++) {
        u = read(), v = read(), d = read();
        Addedge(u, v, d);   
        Addedge(v, u, d);
        Left = std::min(Left, d);
    }
    initation::DFS(1, 0);
    for (int i = 1; i <= n; i++) Right = std::max(Right, dis1[i] + dis2[i]);
    if (m == 1) { printf("%lld", Right); return 0; }
    Right++;
    while (Left <= Right) {
        Mid = (Left + Right) >> 1;
        if (Judge()) ans = Mid, Left = Mid + 1;
        else Right = Mid - 1;
    }
    printf("%lld", ans);
    return 0;
}

朴实沉毅