树网的核

题目

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

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

  $$ 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,他是某直径上的一段路径(该路径两端均为树网中的结点),其长度不超过s(可以等于s),使偏心距ECC(F)最小。我们称这个路径为树网T=(V, E, W)的核(Core)。必要时,F可以退化为某个结点。一般来说,在上述定义下,核不一定只有一个,但最小偏心距是唯一的。

输入输出格式

输入格式

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

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

输出格式:

输出文件core.out只有一个非负整数,为指定意义下的最小偏心距。

输入输出样例

输入样例

5 2

1 2 5

2 3 2

2 4 4

2 5 3

输出样例

5

思路

dfs 直径的一个端点 —-> dfs 从这个端点到达任意一点的距离 —-> dfs 找出一条直径 —–> 对于已经存起来的直径
一边删一边加枚举每一种可行路径然后更新答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cmath>
#define Min(x, y) (x <= y ? x : y)
#define Max(x, y) (x >= y ? x : y)
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag = false, ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) flag |= ch == '-';
for(x = 0; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
x = flag ? -x : x;
}
int n, s;
int tot, h[306], Next[700], to[700], value[700];
int Max_l, dis[500], From;
int q[10000], cnt, a[10000];
inline void add(int u, int v, int w)
{
tot ++; Next[tot] = h[u]; h[u] = tot; to[tot] = v; value[tot] = w;
}
void dfs(int u, int last)
{
if (dis[u] > Max_l) Max_l = dis[u], From = u;
for (int i=h[u]; i; i=Next[i])
{
if (to[i] != last)
{
dis[to[i]] = dis[u] + value[i];
dfs(to[i], u);
}
}
}
void dfs1(int u)
{
q[cnt++] = u;
for (int i=h[u]; i; i=Next[i])
{
if (dis[u] - value[i] == dis[to[i]])
{
a[u] = value[i];
dfs1(to[i]);
}
}
}
inline int work()
{
in(n); in(s);
F(i, 2, n)
{
int u, v, w;
in(u); in(v); in(w);
add(u, v, w); add(v, u, w);
}
dfs(1, -1);
Max_l = dis[From] = 0;
dfs(From, -1);
dfs1(From);
int ans = 1e9, L = 0, R = 0, De = 0, now = 0;
while(a[q[R]])
{
now += a[q[R++]];
while(now > s)
{
now -= a[q[L++]];
De += a[q[L-1]];
}
ans = Min(ans, Max(De, Max_l - now - De));
}
printf("%d\n", ans);
}
int TAT = work();
int main() {;}