文件名称：算法六点双连通分量上的暴力-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:37
集训队论文集
5.2 算法六点双连通分量上的暴力 子任务 5、6满足特殊性质 3，每个点双的大小不超过 4。 Tarjan求点双的过程是这样的：在 DFS的过程中维护一个栈，每次 DFS到点 i的时候， 将点 i压入栈中，然后令计时器加一，并设置 dfn(i)和 low(i)为当前计时器。对于 i的每一 条边 (i, p)进行考虑，如果这条边是返祖边，则用 dfn(p)更新 low(i)；否则 DFS进入 p，返 回后先用 low(p)更新 low(i)，然后若 low(p) ≥ dfn(i)，那么我们找到了一个点双（设为 C）， 从栈中弹栈直到弹出 p为止。设弹出的点集为 S，则我们找到的点双的点集为 VC = S ∪ {i}， 设 i为 C的根。 如果一个点 p在一个点双 C中，且不是 C的根，那么我们就称 p真实属于点双 C，这 样（除了最开始调用 Tarjan 的点，即 DFS 树的根之外）每个点都真实属于一个唯一的点 双。每一个点双都有一个唯一的根，而它的根真实属于另一个点双，因此点双与点双之间 构成了一个有根树森林的结构，其中每个点双的父亲为它的根所在点双（如果存在）。我们 称这个有根树森林为点双树。结合 Tarjan的过程，可以看出 Tarjan相当于是按照 DFS序遍 历点双树。 现在可以考虑在树形结构上进行 DP。设计状态 f (i, d)表示所有点都在以点 i为根的点 双（以及这些点双的子树内的所有点双）中，且满足子图中 i的点度为 d 时的最大点权和 60