[BZOJ 3242][NOI 2013] 快餐店

题目大意

给定一个 $n$ 个节点的环套树,每个边有一个边权。现要找一个点,使得所有的点到这个点的距离的最大值最小,这个点可以在节点上,也可以在边上。求最小的最大值。

$1 \leqslant n \leqslant 100,000$

$1 \leqslant w \leqslant 1,000,000,000$ (边权)

题目链接

BZOJ 3242

UOJ 126

CodeVS 3047

题解

最大值的点一定有两个,快餐店在其中点。如果是树,答案就是直径除以 $2$;现在要求环套树上的,可以考虑删去环上的一条边成为树,答案中的最小值就是最终答案,然而这样会 TLE。

这些直径中,有的会在环的外面(即链上没有环上的边),另一些则经过环,考虑分开计算。

用类似 DP 的方法从环上的点向环外做 dfs,期间可以求出第一类的最长链。

对于第二种,在环上用类似 DP 的方法求出以环的头/尾(从头和从尾各枚举一遍)为起点的最长链(代码中以数组 lenFromStlenFromEd 表示)、在头/尾与当前枚举到的节点间经过环的最长链(在代码中以 chainOnCircleFromStchainOnCircleFromEd 表示),最后枚举删去环上的哪一条边,利用刚刚算出的四个数组计算出第二类的答案。

感觉不错的题。。。对着题解理解了许久(我好菜啊.jpg)。。。

代码

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <algorithm>
// #define DBG
const int MAXN = 100005;
struct Edge;
struct Node {
Edge *e;
Node *fa;
int dfn, len;
long long f;
bool onCircle;
} N[MAXN], *C[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
int w;
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
};
void addEdge(int u, int v, int w) {
N[u].e = new Edge(&N[u], &N[v], w);
N[v].e = new Edge(&N[v], &N[u], w);
}
int circleCnt;
void dfs(Node *u) {
static int dfsClock = 0;
u->dfn = ++dfsClock;
for (Edge *e = u->e; e; e = e->next) {
if (e->v == u->fa) continue;
if (e->v->dfn == 0) {
e->v->fa = u;
e->v->len = e->w;
dfs(e->v);
} else if (e->v->dfn > u->dfn) {
for (Node *c = e->v; c != u; c = c->fa) {
C[++circleCnt] = c;
c->onCircle = true;
#ifdef DBG
printf("circleCnt = %d, len = %d\n", circleCnt, C[circleCnt]->len);
#endif
}
C[++circleCnt] = u;
u->len = e->w;
u->onCircle = true;
#ifdef DBG
printf("circleCnt = %d, len = %d\n", circleCnt, C[circleCnt]->len);
#endif

}
}
}
long long ans1;
void dfs(Node *u, Node *fa) {
for (Edge *e = u->e; e; e = e->next) {
if (e->v == fa || e->v->onCircle) continue;
dfs(e->v, u);
ans1 = std::max(ans1, u->f + e->v->f + e->w);
u->f = std::max(u->f, e->v->f + e->w);
}
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}
dfs(&N[1]);
for (int i = 1; i <= circleCnt; i++) dfs(C[i], NULL);
long long sum = 0, maxTemp = 0;
static long long lenFromSt[MAXN], chainOnCircleFromSt[MAXN];
for (int i = 1; i <= circleCnt; i++) {
sum += i == 1 ? 0 : C[i - 1]->len;
lenFromSt[i] = std::max(lenFromSt[i - 1], sum + C[i]->f);
chainOnCircleFromSt[i] = std::max(chainOnCircleFromSt[i - 1],
C[i]->f + sum + maxTemp);
maxTemp = std::max(maxTemp, C[i]->f - sum);
#ifdef DBG
printf("from st - (%d): len = %lld, chain = %lld\n", i, lenFromSt[i], chainOnCircleFromSt[i]);
#endif
}
sum = maxTemp = 0;
static long long lenFromEd[MAXN], chainOnCircleFromEd[MAXN];
int temp = C[circleCnt]->len;
#ifdef DBG
printf("temp = %d\n", temp);
#endif
C[circleCnt]->len = 0;
for (int i = circleCnt; i; i--) {
sum += C[i]->len;
lenFromEd[i] = std::max(lenFromEd[i + 1], sum + C[i]->f);
chainOnCircleFromEd[i] = std::max(chainOnCircleFromEd[i + 1],
C[i]->f + sum + maxTemp);
maxTemp = std::max(maxTemp, C[i]->f - sum);
#ifdef DBG
printf("from ed - (%d): len = %lld, chain = %lld\n", i, lenFromEd[i], chainOnCircleFromEd[i]);
#endif
}
long long ans2 = chainOnCircleFromSt[circleCnt];
for (int i = 1; i < circleCnt; i++) {
ans2 = std::min(ans2,
std::max(std::max(chainOnCircleFromSt[i],
chainOnCircleFromEd[i + 1]),
lenFromSt[i] + temp + lenFromEd[i + 1]));
#ifdef DBG
printf("i = %d\nmax{%lld, %lld, %lld}\n", i ,
chainOnCircleFromSt[i], chainOnCircleFromEd[i + 1],
lenFromSt[i] + temp + lenFromEd[i + 1]);
#endif
}
#ifdef DBG
printf("ans1 = %lld, ans2 = %lld\n", ans1, ans2);
#endif
double ans = std::max(ans1, ans2) / 2.0;
printf("%.1lf\n", ans);
return 0;
}