NOI2013 快餐店

夏佑 | XiaU

图片炸了,难过。本地也没有存。

Sol.

一道很经典的基环树上dp题。调了一年

首先,如果没有环的话,这就是一道简单的求树上重心的题目。众所周知,树的重心一定在直径的中点上。

但是现在在一个基环树上做,应该怎么求呢?我们先画一个图:

基环树

为了方便,我们先设边权全部为 \(1\)

首先,我们可以想到断一条环上的边,然后求断边后的树的直径。

略证:考虑到直径一定不会经过一整个环,所以依次断边后求直径一定不会漏掉真正的直径。

这样的复杂度是 \(O(n^2)\) 的,我们考虑一下如何优化。

在刚刚的过程中,我们从环上的第一条边一直到最后一条边依次断开,而我们每次断开都要重新计算一次直径,这中间显然是有重合的部分的,于是我们可以考虑用类似于 dp 的东西优化。

考虑有两种情况:

  1. 直径没有经过环;
  2. 直径经过了环。

第一个情况很好搞,第二种情况略有麻烦,也是我们刚刚复杂度的瓶颈所在。

先上结论:

  • \(pre_i\) 表示 \(i\) 点之前某以环上节点为根节点的子树的直径加上该点距离环上 \(1\) 号点的距离的最大值;
  • \(suf_i\) 表示 \(i\) 点之后某以环上节点为根节点的子树的直径加上该点距离环上 \(m\) 号点的距离的最大值;
  • \(pres_i\) 表示 \(i\) 点之前环上某两节点的子树直径加上两点之间的距离的最大值;
  • \(sufs_i\) 表示 \(i\) 点之后环上某两节点的子树直径加上两点之间的距离的最大值;
  • \(w_{(i,j)}\) 表示 \(i,j\) 两点的距离。

那么第 \(i\) 号点的答案即为 \(\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\)

最终答案即为 \(\min\limits_{i=1}^{m-1}\{\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\}\)

是不是到现在已经有些晕了?没关系,我们从图上举例说明一下。

删边

例如,我们现在有一只删了一条环边 \((4,5)\) 的基环树。

我们仔细复盘一下刚刚的几句话。

先看 \(pre_i\)\(suf_i\)。由于两个很像,所以重点解释 \(pre_i\)

\(pre_i\) 表示 \(i\) 点之前 \(//\) 某以环上节点为根节点的子树的直径 \(//\) 加上该点距离环上 \(1\) 号点的距离 \(//\) 的最大值。

形式化的来说,我们要找的就是:

\(pre_i=\max\limits_{j=1}^{i}\{dep_j+w_{(1,j)}\}\)

来看张图。

pre和suf

可能有多种方案,图中仅展示一种。

图中绿色的部分即为 \(pre_4\),橙色的部分即为 \(suf_5\)

可以看出来 \(pre_i\)\(suf_i\) 其实就是一棵子树的直径 \(+\) 它前面(后面)的链的长度。

接下来再看看 \(pres_i\)\(sufs_i\),同样重点解释 \(pres_i\)

\(pres_i\) 表示 \(i\) 点之前 \(//\) 环上某两节点的子树直径 \(//\) 加上两点之间的距离的最大值。

形式化的来说,我们要找的就是:

\(pres_i=\max\limits_{j=1}^{i}\{dep_i+dep_j+w_{(i,j)}\}\)

再来看张图。

pres和sufs

可能有多种方案,图中仅展示一种。

图中蓝色的部分即为 \(pres_4\),黄色的部分即为 \(sufs_5\)

好,弄清楚这 \(4\) 个,我们来看看结果的式子:

那么第 \(i\) 号点的答案即为 \(\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\)

我们考虑到删掉边 \((i,i+1)\) 的时候,直径有三种可能:

  1. 直径在 \([1,i]\) 之间;
  2. 直径在 \([i+1,m]\) 之间;
  3. 直径跨过了边 \((1,m)\)

对于第一种情况,我们惊喜地发现,\(pres_i\) 即为我们所求。

对于第二种情况,我们再次惊喜地发现,\(sufs_{i+1}\) 即为我们所求。

对于第三种情况,我们发现,由于 \(pre_i\) 一直延伸到 \(i\)\(suf_{i+1}\) 一直延伸到 \(m\),所以我们再加上 \(w_{(1,m)}\) 即可,也就是 \(pre_i+suf_{i+1}+w_{(1,m)}\)

最后我们遍历一遍,统计最小值即可。

Code

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 7;

struct Edge
{
int to, nxt, w;
}e[MAXN << 1];

int n;

int head[MAXN << 1], ent;
int fa[MAXN], tnt, dfn[MAXN], dis[MAXN];
bool iscyc[MAXN];
int cyc[MAXN], cnt, cycdis[MAXN];
ll dep[MAXN];
ll pre[MAXN], suf[MAXN], presub[MAXN], sufsub[MAXN];
ll ans = 0;

void add_edge(int u, int v, int w)
{
e[++ent].to = v;
e[ent].w = w;
e[ent].nxt = head[u];
head[u] = ent;
}

void dfs1(int u)
{
dfn[u] = ++tnt;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if(v == fa[u]) continue;
if(!dfn[v])
{
fa[v] = u;
dis[v] = e[i].w;
dfs1(v);
}
else if(dfn[v] > dfn[u])
{
for(; v != u; v = fa[v])
{
iscyc[v] = true;
cyc[++cnt] = v;
cycdis[cnt] = dis[v];
}
iscyc[u] = true;
cyc[++cnt] = u;
cycdis[cnt] = e[i].w;
}
}
}

void dfs2(int u, int father)
{
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if(!iscyc[v] && v != father)
{
dfs2(v, u);
ans = max((ll)dep[u] + dep[v] + e[i].w, ans);
dep[u] = max(dep[u], dep[v] + e[i].w);
}
}
}

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add_edge(a, b, c);
add_edge(b, a, c);
fa[i] = i;
}
dfs1(1);
for(int i = 1; i <= cnt; i++)
dfs2(cyc[i], 0);
ll sum = 0, maxdep = 0;
for(int i = 1; i <= cnt; i++)
{
sum += cycdis[i - 1];
pre[i] = max(pre[i - 1], dep[cyc[i]] + sum);
presub[i] = max(presub[i - 1], sum + maxdep + dep[cyc[i]]);
maxdep = max(maxdep, dep[cyc[i]] - sum);
}
sum = maxdep = 0;
int tmp = cycdis[cnt];
cycdis[cnt] = 0;
for(int i = cnt; i; i--)
{
sum += cycdis[i];
suf[i] = max(suf[i + 1], dep[cyc[i]] + sum);
sufsub[i] = max(sufsub[i + 1], sum + maxdep + dep[cyc[i]]);
maxdep = max(maxdep, dep[cyc[i]] - sum);
}
ll res = presub[cnt];
for(int i = 1; i < cnt; i++)
res = min(max(max(presub[i], sufsub[i + 1]), pre[i] + suf[i + 1] + tmp), res);
printf("%.1lf", (double)max(ans, res) / 2.0);
return 0;
}
  • 标题: NOI2013 快餐店
  • 作者: 夏佑 | XiaU
  • 创建于 : 2022-09-01 00:00:00
  • 更新于 : 2023-09-15 09:13:54
  • 链接: https://summace.cc/LGP1399/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
此页目录
NOI2013 快餐店