树的中心

Cover Image

CAUTION
本文含有大段写得很丑的 Golang,可能会引起不适(

题目描述
蓮子和梅莉玩游戏。梅莉掏出一棵无根树,要蓮子在规定时间内确定一个点,使得这个点到其他点的最长路径最小,蓮子是一个只会 AK IPhO 的巨佬,所以她请教你帮她,事成之后就和梅莉结婚。
输入格式
第 1 行一个数 n 接下来 n-1 行,每行 u,v,w 表示从 u 和 v 之间有有一条权为 w 的无向边。
输出格式
一个数,表示使最大路径最小的点的编号。
HINT
对于 100% 的数据 1≤n≤1,000,000。

这是一个树形 DP 的准模板题,所以直接放一个很丑的 Golang 写法:

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
76
77
78
79
80
81
82
83
84
85
86
package main

import . "fmt"

const N = 2e6 + 2

var index int
var f [N] int
var g [N] int
var h [N] int
var up [N] int
var head [N] int
var next [N] int
var edge [N] int
var vertex [N] int

func maxInt(x, y int) int {
if x > y {
return x
}
return y
}

func link(u, v, w int) {
index++
vertex[index] = v
edge[index] = w
next[index] = head[u]
head[u] = index
index++
vertex[index] = u
edge[index] = w
next[index] = head[v]
head[v] = index
}

func initialize(u, fa int) {
for i := head[u]; i != 0; i = next[i] {
var v, w = vertex[i], edge[i]
if vertex[i] == fa {
continue
}
initialize(v, u);
if f[u] < f[v] + w {
g[u] = f[u]
f[u] = f[v]+w
up[u] = v
} else if g[u] < f[v] + w {
g[u] = f[v] + w
}
}
}

func dfs(u, fa int) {
var v, w int
for i := head[u]; i != 0; i = next[i] {
v, w = vertex[i], edge[i]
if vertex[i] == fa {
continue
}
if v == up[u] {
h[v] = maxInt(h[u], g[u]) + w
} else {
h[v] = maxInt(h[u], f[u]) + w
}
dfs(v, u)
}
}

func main() {
var n, ans, u, v, w int
ans = 1
Scan(&n)
for i := 1; i < n; i++ {
Scan(&u, &v, &w)
link(u, v, w)
}
initialize(1, 1)
dfs(1, 1)
for i := 2; i <= n; i++ {
if maxInt(f[i], h[i]) < maxInt(f[ans], h[ans]) {
ans = i
}
}
Print(ans)
}

Download

第一次用 Golang 做题就被劝退了。所以 🍞 说得对:

C with STL 比 Golang 不知道高到哪里去了:

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
#include <cstdio>
#include <algorithm>
using std::max;
const int N=2e6+2;
int fp,hed[N],nxt[N],edg[N],ver[N],f[N],g[N],h[N],up[N];
int read() {
int x=0;char c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x*=10;c=getchar();}
return x;
}
void link(int u,int v,int w) {
ver[++fp]=v;edg[fp]=w;nxt[fp]=hed[u];hed[u]=fp;
ver[++fp]=u;edg[fp]=w;nxt[fp]=hed[v];hed[v]=fp;
}
void init(int u,int fa) {
for(int i=hed[u],v,w;i;i=nxt[i]) {
v=ver[i],w=edg[i];
if(ver[i]==fa) continue;
init(v,u);
if(f[u]<f[v]+w) g[u]=f[u],f[u]=f[v]+w,up[u]=v;
else if(g[u]<f[v]+w) g[u]=f[v]+w;
}
}
void dfs(int u,int fa) {
for(int i=hed[u],v,w;i;i=nxt[i]) {
v=ver[i],w=edg[i];
if(ver[i]==fa) continue;
if(v==up[u]) h[v]=max(h[u],g[u])+w;
else h[v]=max(h[u],f[u])+w;
dfs(v,u);
}
}
int main() {
int n=read(),ans=1;
for(int i=1,u,v,w;i<n;++i)
u=read(),v=read(),w=read(),link(u,v,w);
init(1,1);dfs(1,1);
for(int i=2;i<=n;++i)
if(max(f[i],h[i])<max(f[ans],h[ans])) ans=i;
printf("%d",ans);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。