[题解] [IOI2008] Island

[题解] [IOI2008] Island

给出一个 $n$ 个点的基环树森林(每一个点有一条无向边),让你求出所有基环树的直径(即一条不经过重复点的基环树上的最长路径)之和。

$2\le n\le 10^6$

题目链接


思路

我们考虑不使用邻接表,而是只记录一个点的边的目标位置( $tar_x$ )和这条边的长度 ( $wei_x$ )。

我们发现对于一个在环上的点 $x$,$tar_x$ 必定是这个环上的另一个点。而对于不在环上的点,它们必定构成一个树形结构,而且所有树的根的 $tar$ 必定是一个环上的点。很容易理解,不加说明。

下面,对于基环树环上的每个点 $x$ ,我们称不在环上 $tar$ 为 $x$ 的所有树和 $x$ 共同组成的集合为外环树(自己瞎造的名字)。举个例子:

为什么莫名有一种喜感

这里的 1、2、3 都是环上的点。那么 1 的外环树就是 ${1,5,6,7,8}$,2 的外环树是 ${2}$ ,3 的外环树是 ${3,4}$。

我们记一个点 $x$ 的外环树的直径为 $g_x$ ,外环树上从 $x$ 开始的最长链的长度为 $f_x$。同样以上面那张图为例子,那么 $f_1$ 就是 7(3+4),$g_1$ 就是 8(4+1+3)。

我们发现,一个基环树的直径要不是一个外环树的直径,要不就是 $f_i$ +($i \to j$)+ $f_j$ ( $i,j$ 都是环上的点)。

第二种情况可能不太好理解。以上图为例,$4\to 3\to 2\to 1\to 5\to 7$ 就属于是第二种情况。

那么接下来就简单了。我们只需要用拓扑序处理出每一个环上的点的 $f$ 和 $g$,然后再对于每一个环处理。我们从任意一个点开始,将整个环转换为一条链(比如上图中的环从 1 开始会变成 $[1,2,3]$ ,然后从左到右扫。我们注意到,对于两个点 $i$ 和 $j$($i$ 在数组中的位置小于 $j$),$(i\to j)$ 事实上是可以选择两条不同的路径(如上图 $(1\to 2)$ 可以是 $1\to 2$ 或 $1\to 3\to 2$。因此我们令环上路径长度的前缀和为 $pre$,环的路径总长度为 $len$,再记(下面 $i$ 的下标小于 $j$):
$$
\begin{aligned}
ret1&=\max{f_i+f_j+pre_j-pre_i}\
ret2&=\max{f_i+f_j+len-(pre_j-pre_i)}
\end{aligned}
$$
我们发现 $i$ 和 $j$ 的贡献在上面两个式子中是独立的,我们可以记一下当前下标小于 $j$ 的 所有 $i$ 中最大的 $f_i-pre_i$( $m1$ ) 和 $f_i+pre_i$( $m2$ ),然后每次新扫到一个点就可以用 $m1$ 和 $m2$ 更新。

那么最后的答案就是($i$ 为环上的点):
$$
ans=\max{ret1,ret2,g_i}
$$
对于每一个环扫一遍即可。


小优化:

  • 我们再遍历完一个环之前并没法拿到这个环的长度 $len$,因此我们更新 $ret2$ 时不加上 $len$,最后遍历完后再给 $ret2$ 加上 $len$ 即可。

  • 我们可以把 $g_i$ 顺便统计到 $ret1$ 里面,并没有什么用


代码

494ms / 30.84MB,目前洛谷2nd最优解

mivik.h

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
// Mivik 2020.8.22
#include <mivik.h>

#include <algorithm>
#include <climits>

MI cin;

typedef long long qe;

const int nmax = 1000005;

template<typename T> inline bool gmax(T& a, const T& b) { return a < b && (a = b, true); }

int n;
int tar[nmax], wei[nmax];
// deg -> degree 度数
int deg[nmax];
qe f[nmax], g[nmax];
inline qe loop(int x) {
const int beg = x;
qe m1 = f[x], m2 = f[x];
qe pre = wei[x];
qe ret1 = g[x];
x = tar[x];
qe ret2 = LLONG_MIN;
while (x != beg) {
deg[x] = 0;
gmax(ret1, f[x] + pre + m1);
gmax(ret2, f[x] - pre + m2);
gmax(ret1, g[x]);
gmax(m1, f[x] - pre);
gmax(m2, f[x] + pre);
pre += wei[x];
x = tar[x];
}
return std::max(ret1, ret2 + pre);
}
int main() {
cin > n;
for (int i = 1; i <= n; ++i) {
cin > tar[i] > wei[i];
++deg[tar[i]];
}
static int q[nmax];
int head = 1, tail = 0;
for (int i = 1; i <= n; ++i) if (!deg[i]) q[++tail] = i;
// 计算出环上每个点的 f[i] 和 g[i]
while (head <= tail) {
const int x = q[head++];
const qe cc = f[x] + wei[x];
gmax(g[tar[x]], f[tar[x]] + cc);
gmax(g[tar[x]], g[x]);
gmax(f[tar[x]], cc);
if (!(--deg[tar[x]])) q[++tail] = tar[x];
}
qe ans = 0;
for (int i = 1; i <= n; ++i) // 如果 deg[i] 不为 0 代表 i 是在环上
if (deg[i]) ans += loop(i);
cout < ans < endl;
}
作者

Mivik

发布于

2020-08-23

更新于

2021-05-31

许可协议

评论