11080: 【原1080】小F的公寓

题目

题目描述

author: duruofei 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1080

Description

改编自 NOIP2006 树网的核.

小F所在的城市“爱吃米”是一个连通无圈的无向图，每个节点是一幢公寓，两两公寓之间由长度不同的道路相连。

“爱吃米”为了方便大家吃米，两两公寓之间都存在唯一一条简单路径。

我们用d(a,b)表示以a,b两个公寓为端点的路径的长度，它是该路径上各道路长度之和。我们称d(a,b)为a,b两公寓间的距离。

一个公寓 v 到一条路径 P 的距离为该公寓与 P 上的最近的公寓的距离：

\( d(v，P) = min { d(v，u)，u为路径 P 上的公寓 } \) 。

“爱吃米”的直径：“爱吃米”中最长的路径称为“爱吃米”的直径。

对于给定的城市T，直径不一定是唯一的，但可以证明：

各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为“爱吃米”的中心。

偏心距ECC(F)：“爱吃米” T 中距路径 F 最远的结点到路径 F 的距离，即 \( ECC(F) = max{ d(v,F), v∈V } \)。

任务：对于给定的城市 T = (V, E,W ) 和非负整数 s ，小F想请你找一个路径 F ，把这个路径上所有的公寓全部租下来。

但是， F 必须是某直径上的一段路径（该路径两端均为城市中的公寓结点），其长度不超过s（可以等于s），使偏心距ECC(F)最小。

我们称这个路径为城市 T = ( V , E, W) 的核（Core）。

必要时，F可以退化为单个公寓结点。

一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

样例中，A-B 与 A-C 是两条直径，长度均为20。点 W 是“爱吃米”的中心，EF 边的长度为5。

如果指定 s = 11，则“爱吃米”的核为路径 DEFG（也可以取为路径 DEF ），偏心距为 8 。

如果指定s=0（或s=1、s=2），则“爱吃米”的核为结点F，偏心距为12。

Input Format

输入包含n行：

第1行，两个正整数n和s，中间用一个空格隔开。其中n为树网结点的个数，s为树网的核的长度的上界。设结点编号依次为1, 2, ..., n。

从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。

所给的数据都是正确的，不必检验。

Output Format

输出只有一个非负整数，为指定意义下的最小偏心距。

说明

20分的数据满足：\( 5 \leq n \leq 15 \)。

70分的数据满足：\( 5 \leq n \leq 80 \)。这里枚举直径，Floyd，枚举core，枚举树外的点都可以做掉。

100分的数据满足：\( 5 \leq n \leq 300, 0 \leq s \leq 1000 \)。边长度为不超过1000的正整数。

100分部分改编自NOIP2007第四题。

110分的数据满足：\( 5 \leq n \leq 500000, 0 \leq s \leq n \) 。最后结果不超过\( 2^{31}-1 \)。

解题思路：

本题是NOIP题目，由于数据范围很小，O（N3）、O（N2）、O（N×S）等复杂度的算法都可以获得满分，但实际上存在更优秀的算法。

题目中要求找的路径必须在树的直径上，如果直接按照描述来，需要找出树的所有直径，而树的直径最多可以是O（N2）级别的，

这样做的话最终复杂度必然会很高，所以必须先对此作出简化。

树的直径虽然可能很多，但它们的形态是很有规律的，题目描述中就已经给了我们一个很有用的规律：

所有直径的中点是重合于树的中心。

我们从最简单的情况入手：树有多条直径，长度均为D，所有直径唯一的交集就是树的中心（那么树的中心一定处于一个结点上）。

那么显而易见，树的形态应该是这样的：从树的中心出发有4条以上没有交集的长度为D／2的路径，不妨称它们为半径。

显然无论怎样选择核的位置，它最多只能覆盖到两条半径，那么偏心距不可能小于D／2，而直接选择树的中心作为核，

偏心距就已经是D／2了，所以树的中心就是核，而这个核位于所有的直径上。

如果所有直径的交集不是一个点呢？由于直径是树上的连续路径，而两条连续路径的交集如果不是空集，一定也是连续路径。

而题目已经告诉了我们，所有直径必定是有交集的，那么交集不是一个点的话，就必然是一段连续的路径，设这个交集为W。

每一条直径都是W两头再延伸出去一段路径形成的，稍加分析就能证明，对于W的某一头，直径延伸出去的所有路径长度都是相等的，

即如下图（红色部分为W，蓝色部分为直径延伸出去的部分）：

联系前面讨论的“交集为一个点”的情况，会发现这里情况是类似的，如果核覆盖到了蓝色的边，那么将核在蓝色边上的部分删掉，偏心距是不会变化的，所以核一定是在红色的部分上的，换句话说：核在任意一条直径上，这和前一种情况得出的结论是相同的。

有了这个结论，我们就可以随便找出一条树的直径，再在上面找核了。找树的直径可以使用动态规划算法或者两次dfs的方法，复杂度均为O（N），具体方法不在此文叙述。下面来研究怎样找到核的位置。

一条直径上最多有O（N）个点，那是否有O（N2）种核的选择方案呢？注意到这样一个性质，向一条路径多加入一条边，偏心距是不会变得更大的，所以如果核在直径上的起点确定了，就可以一直沿着直径向下走，直到走到头或者总长度将要超过S为止，这样一来，核就只有O（N）种选择方案了。

当选定了一种核的位置后，就需要确定它的偏心距。因为核完全位于直径上，所以任意点要走到核上，一定要先走到直径上，不妨将其走到直径上的第一个点称为“进入点”。由于我们只关心离核最远的点的距离，所以树的结构可以简化为链：对于直径上的每个点，找出以它作为进入点的点中距离最远的一个，称为最远旁枝，这一步是O（N）的。现在要确定核的偏心距，它由三部分产生，第一部分是核上所有点的最远旁枝，第二部分是核头部距离直径头部的距离，第三部分是核尾部距离直径尾部的距离。后两个部分很容易得到，对于第一个部分，实际上是一个RMQ问题，当然可以使用各种RMQ算法解决。但事实上，RMQ也是不必要的，因为我们是从前向后在直径上枚举核的起点，终点的位置也是不会回头的，所以实现一个单调队列就可以在O（N）的时间复杂度解决这个问题。

综合以上所述的各个步骤，整个算法的复杂度O（N），和输入规模同阶，已经是理论下界。

Sample Input

Sample Output

FineArtz's solution

/* 小F的公寓 */
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 500005, INF = 2147483647;

class Edge{
public:
    Edge() = default;
    Edge(int uu, int vv, int ww, int nn) : u(uu), v(vv), w(ww), next(nn) {}
    int u = 0, v = 0, w = 0, next = 0;
};

Edge e[MAXN];
int head[MAXN], cnt = 0;
int n, s;
int dist[MAXN], father[MAXN];
int p1, p2;

int q[MAXN] = {0};
bool v[MAXN] = {0};

void addEdge(int u, int v, int w){
    e[++cnt] = Edge(u, v, w, head[u]);
    head[u] = cnt;
}

int dis(int x, int indicator){
    memset(q, 0, sizeof(q));
    memset(v, 0, sizeof(v));
    int front = 0, rear = 0, ret = 0;
    if (indicator){
        for (int i = p2; i != 0; i = father[i])
            v[i] = true;
    }
    v[x] = true;
    q[rear++] = x;
    dist[x] = 0;
    if (!indicator)
        father[x] = 0;
    while (front != rear){
        int now = q[front++];
        for (int i = head[now]; i != 0; i = e[i].next){
            int next = e[i].v;
            if (!v[next]){
                dist[next] = dist[now] + e[i].w;
                if (!indicator)
                    father[next] = now;
                if (dist[ret] < dist[next])
                    ret = next;
                q[rear++] = next;
                v[next] = true;
            }
        }
    }
    return ret;
}

int main(){
    cin >> n >> s;
    for (int i = 1; i < n; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    p1 = dis(1, 0);
    p2 = dis(p1, 0);
    int ans = INF, p = p2;
    for (int i = p2; i != 0; i = father[i]){
        while (father[p] != 0 && dist[i] - dist[father[p]] <= s)
            p = father[p];
        ans = min(ans, max(dist[p], dist[p2] - dist[i]));
    }
    for (int i = p2; i != 0; i = father[i])
        dis(i, 1);
    for (int i = 1; i <= n; ++i)
        ans = max(ans, dist[i]);
    cout << ans << endl;
    return 0;
}