题解 P4796 【[BalticOI 2018]路径】

· · 题解

Paths

路径

翻译自 BalticOI 2018 Day 2 题解

子任务 1

暴力枚举所有合法的路径就可以得到子任务 1 的分数（见下面的算法，去掉记忆化搜索和动态规划部分以达到指数级复杂度）。

子任务 2

因为颜色数最多为 3，所以路径的长度最多为 3，即路径的长度为 2 或 3。长度为 2 的路径条数容易计算：即起点和终点颜色不同的边的条数。长度为 3 的路径条数需要更多的思考。我们可以通过枚举路径中间的一个点是哪一个点与起点终点的颜色来处理这个问题。那么以这个点为中间节点的路径条数就是与中间点相连的第一个颜色的点的个数和与中间点相连的第二个颜色的点的个数的乘积。

子任务 3

子任务 3 是对子任务 2 的自然延伸。我们不枚举中间点是什么，而是枚举中间的一条边是什么，其余部分与子任务 2 完全一致。

子任务 4

假设存在一个函数 f 表示以某个点为起点的合法路径条数。那么答案就是对所有点的 f 函数求和。关键在于因为数据很大，如何高效地计算函数 f 的值。

令函数 f 有两个参数 c（当前点）与 C （一个表示目前已经用过的颜色的 bitset，初始为 0）。由于一条路径上的颜色个数最多为 5，所以这样的 bitset 最多有 2^5=32 个。这意味着函数 f(c,\,C) 的参数的组合数小到我们可以打表：我们使用动态规划算法。

对参数 c 和 C 进行记忆化搜索，我们需要对所有相邻 c 和 C 将函数 f(c',\,C') 的值求和，其中 C' 为与 C 相同的 bitset，但是表示颜色 c 的二进制位被标记了。我们保证不重复使用颜色，并且不会重复计算之前计算过答案的状态的答案。如此以来，问题的答案就是 \sum f(i,\, 0) （需要保证不要计算长度为 1 的路径！），还要注意使用 64 位整数。

算法的时间复杂度为 \mathcal{O}(2^{K}N)。

有趣的一些东西：这个问题实质上是关于统计最大长度为 k 的各点颜色不相同的路径条数。这个问题比计算长度最大为 k! 的 所有 路径条数简单。后者暴力算法的复杂度为 n^k 而不是 2^kn。这种思想可以作为一种通用算法技术提高多种问题的求解速度：多次随机选择颜色（严格的说，O((\log n)^k) 次），然后使用一种限制各点颜色不同的算法。