T292589 蟠桃仙塔（tower） 题解

zrl123456 · 2025-11-26 22:31:29 · 题解

:::::info[题目基本信息] 考察：搜索，图论（中下位紫？）。
题目简介：
给定 n，有 n 个物品，价值为 \{w_n\}，两端（可以钦定哪端是首段，哪端是尾端）颜色分别为 \{s_n\},\{t_n\}，现在你需要选取一些物品，将它们按任意顺序排列，将它们拼接，要求拼接的相邻物品中前一个物品的尾端颜色和后一个物品的首端颜色相同，你的得分就是选取的物品的价值总和，问得分最大是多少。
数据范围：

• 1\le n\le 5\times 10^5
• \forall i\in[1,n],1\le w_i\le 1000
• \forall i\in[1,n],1\le s_i,t_i\le\color{red}4

  ::::: 见二连边还在追我，容易想到对于每一个物品连一条 s_i\leftrightarrow t_i 的边，然后你观察到里面有很多很多的重边，考虑怎么利用。
  有一个比较重要的性质：

• :::::success[证明] 这个性质是比较显然的。因为两条边就足够你来回一次了，剩下的边自然可以缩成一个自环单独处理。 ::::: 然后我们注意到对于所有可达点自环都能被记进贡献内（注意当原图就有多条自环时同样需要根据上面方式保留最多两条边），然后发现对于剩下的边我们可以直接爆搜，于是就有了下面的算法流程：
• 枚举点集子集，使用并查集判断它们是否联通，若不联通枚举下一个子集。
• 对于一个子集先累加自环贡献，然后对于剩余的边直接爆搜所有路径即可。

:::::success[优化] 在爆搜中，对于一个点，我们对于通向同一个点的边只选择价值最大的那条递归，容易证明正确性，实测运行时间缩小到原来的 \dfrac{1}{60}。
::::: 这样我们就做完了此题。
时空复杂度玄学。

code