洛谷 P1099 [NOIP 2007 提高组] 树网的核-普及+/提高

P1099 [NOIP 2007 提高组] 树网的核

题目描述

设 $T=(V,E,W)$ 是一个无圈且连通的无向图（也称为无根树），每条边都有正整数的权，我们称 $T$ 为树网（treenetwork），其中 $V$，$E$ 分别表示结点与边的集合，$W$ 表示各边长度的集合，并设 $T$ 有 $n$ 个结点。

路径：树网中任何两结点 $a$，$b$ 都存在唯一的一条简单路径，用 $d(a,b)$ 表示以 $a,b$ 为端点的路径的长度，它是该路径上各边长度之和。我们称
$d(a,b)$ 为 $a,b$ 两结点间的距离。

D(v,P)=min⁡{d(v,u)}D(v, P)=\min\{d(v, u)\}D(v,P)=min{d(v,u)}, $u$ 为路径 $P$ 上的结点。

树网的直径：树网中最长的路径称为树网的直径。对于给定的树网 $T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距 $\mathrm{ECC}(F)$：树网 $T$ 中距路径 $F$ 最远的结点到路径 $F$ 的距离，即

ECC(F)=max⁡{D(v,F),v∈V}\mathrm{ECC}(F)=\max\{D(v, F),v \in V\}ECC(F)=max{D(v,F),v∈V}

任务：对于给定的树网 $T=(V,E,W)$ 和非负整数 $s$，求一个路径 $F$，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 $s$（可以等于 $s$），使偏心距 $\mathrm{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$。

输入格式

共 $n$ 行。

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

5

输入输出样例 #2

输入 #2

8 6
1 3 2
2 3 2 
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

输出 #2

5

说明/提示

• 对于 $40\%$ 的数据，保证 $n\le 15$。
• 对于 $70\%$ 的数据，保证 $n\le 80$。
• 对于 $100\%$ 的数据，保证 $2\le n\le 300$，$0\le s\le 10^3$，$1\le u,v\le n$，$0\le w\le 10^3$。

NOIP2007 提高组第四题

solution

• 1 以节点 1 为根，dfs 找到到距离根最远的点a，则 A 为直径的一个端点
• 2 以节点 A 为根，找到任意节点 u 的最远分支长度 f[u], 次远分支长度 g[u], 和 A 的距离 d[u], 和 d[u] 最大的点 B(直径的另一个端点)，父节点 fa[u], 到父节点到距离 fw[u]
• 3 从 B -> A 搜索，先找 ans = max(g[u]), 然后在直径两端删除一部分，使得剩余部分长度不超过 s，并且尽可能使得中间部分的端点和中点的距离最大值最小，然后删除的部分也考虑到 ans 中即可

代码

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"
#include "cstring"using namespace std;/** P1099 [NOIP 2007 提高组] 树网的核* 题目大意：一个有权无根树，n (2<=n<=300) 个节点, 核为直径(树中最长的简单路径)中的一段路径，须满足其它点到它的距离的最大值最小* 核长度不超过s(0<=s<=1000)时，求所有点到核距离最大值** 思路：* 1 以节点 1 为根，dfs 找到到距离根最远的点a，则 A 为直径的一个端点* 2 以节点 A 为根，找到任意节点 u 的最远分支长度 f[u], 次远分支长度 g[u], 和 A 的距离 d[u], 和 d[u] 最大的点 B(直径的另一个端点)*      父节点 fa[u], 到父节点到距离 fw[u]* 3 从 B -> A 搜索，先找 ans = max(g[u]), 然后在直径两端删除一部分，使得剩余部分长度不超过 s，并且尽可能使得中间部分的端点和中点的距离最大值最小*/typedef pair<int, int> pii;
const int N = 3e2 + 5;int n, s, d[N], fa[N], fw[N], A, B, dis, f[N], g[N];
vector<pii> e[N];// 以 1 为 root，找最远距离的 A 点
void dfs(int u, int p, int ds) {for (auto [v, w]: e[u])if (v != p) {dfs(v, u, ds + w);}if (ds > dis) dis = ds, A = u;
}// 以 A 为 root，找直径中的点到 A 的距离
void dfs2(int u, int p) {for (auto [v, w]: e[u]) {if (v != p) {d[v] = d[u] + w;fw[v] = w, fa[v] = u;dfs2(v, u);if (f[v] + w > f[u]) g[u] = f[u], f[u] = f[v] + w;else if (f[v] + w > g[u]) g[u] = f[v] + w;}}if (d[u] > dis) dis = d[u], B = u;
}int main() {cin >> n >> s;for (int i = 1, x, y, w; i < n; i++) {cin >> x >> y >> w;e[x].emplace_back(y, w);e[y].emplace_back(x, w);}dfs(1, 0, 0);dis = 0;dfs2(A, 0);int u, ans = 0;vector<int> t;for (u = B;; u = fa[u]) {ans = max(ans, g[u]);t.push_back(u);if (u == A) break;}int x = 0, y = 0, i = 0, j = t.size() - 1;while (x + y < dis - s) {if (x + fw[t[i]] < y + fw[t[j - 1]]) {x += fw[t[i++]];} else{y += fw[t[--j]];}}ans = max(ans, f[t[i]]);ans = max(ans, d[t[j]]);cout << ans << endl;return 0;
}

结果