Skip to content

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

5 2
1 2 5
2 3 2
2 4 4
2 5 3

Sample Output

5

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