广义串并联图

Para · 2023-01-25 21:21:55 · 个人记录

定义

广义串并联图是指一类满足任意 4 个节点都不存在 6 条两两没有公共边的路径连接这些点的无向连通图。

可以看出，一般的树或者仙人掌都是满足广义串并联图的性质的。且运用该算法的一些化简思想也是值得学习的。

性质

• 广义串并联图可以通过若干次删 1 度点，缩 2 度点，复合重边最终变为一个单点。证明应该可以使用反证法，设每个点度数都至少为 3 推导，具体证明可以看论文。

习题

2019 集训队互测 Day 3 公园

题目链接

例题。基本按照论文中的顺序，感觉是不错的引入顺序。

广义串并联图中化简问题三种手段删 1 度点，缩 2 度点，复合重边。我们依次考虑，假设没有修改操作。

我们先将一条边会带来的贡献扩展一下 w_{0/1,0/1} 表示两侧分别为黑白带来的贡献。

删 1 度点：

对于一个叶子节点 v，设其父亲节点为 u。

当 u 节点为白色，v 能够带来的最大贡献为 \max(w_{(u,v),1,1} + w_v, w_{(u,v),1,0} + b_v)，为黑色时最大贡献为 \max(w_{(u,v),0,0} + b_v, w_{(u,v),0,1} + w_v)。

那么可以视为 w_u 增加 \max(s_{(u,v)} + w_v, d_{(u,v)} + b_v)，b_u 增加 \max(s_{(u,v)} + b_v, d_{(u,v)} + w_v)，并删除 v 点。

缩 2 度点：

假设 x 出度为 2，连接的两节点分别为 u,v。

• w_{0,0} = \max(w_{(u,x),0,0} + b_x + w_{(x,v),0,0}, w_{(u,x),0,1} + w_x + w_{(x,v),1,0})
• w_{0,1} = \max(w_{(u,x),0,0} + b_x + w_{(x,v),0,1}, w_{(u,x),0,1} + w_x + w_{(x,v),1,1})
• w_{1,0} = \max(w_{(u,x),1,0} + b_x + w_{(x,v),0,0}, w_{(u,x),1,1} + w_x + w_{(x,v),1,0})
• w_{1,1} = \max(w_{(u,x),1,0} + b_x + w_{(x,v),0,1}, w_{(u,x),1,1} + w_x + w_{(x,v),1,1})

可视作删除 x 点并在 u,v 之间连上 w。

复合重边：

直接将对应边权相加即可，注意点对 (u,v) 是有序的。

没有修改的情况就可以按照上述方案缩图得到最终答案，接下来考虑有修改的情况。可以将图变化带来贡献变化建树，用矩阵维护带来的影响。动态 \text{dp} 维护。

每次都把好端端的题做成 * 喂给人吃，不愧是某毒瘤出题人，代码天气好了再写。

SNOI2020 生成树

题目链接

设 f_{i,0/1} 表示第 i 条边等价保留/删的局部方案数。

删 1 度点：答案 \times f_{i,0}

缩 2 度点：

假设 x 出度为 2，连接的两节点分别为 u,v。

• f_0 = f_{(u,x),0} \times f_{(x,v),0}
• f_1 = f_{(u,x),0} \times f_{(x,v),1} + f_{(u,x),1} \times f_{(x,v),0}

可视作删除 x 点并在 u,v 之间连上 f。

复合重边：

• f_0 = f_{i,0} \times f_{j,1} + f_{i,1} \times f_{j,0}
• f_1 = f_{i,1} \times f_{j,1}

JOI Open 2022 放学路

题目链接

按照广义串并联图的思想，对于除了 1,n 以外的节点删 1 缩 2，缩重边时出现边权不同时打个 \text{tag}。

接着通过观察可以发现，如果我们将 1 \rightarrow n 路径上一定不会经过的点删除，就只需要判断边 (1, n) 与是否存在其他点。

删除一定不会经过的点可以通过在 (1,n) 之间连边，只考虑包含 1,n 的点双即可。

证明可以先构造从 1 到 n 的一条链，接着在这些点之间连边满足度数 \ge 3 的限制，边权为它们之间的距离。可以发现，若两条边有重合一定有解。显然无法构造出非法情况。

余姚中学 2019 联测 Day 1 有限空间跳跃理论

题目链接

求解无向图定向后为 \text{DAG} 的方案数。

常见方法是考虑每一次新加入一层出度为 0 的节点，由于同一批点可能分多次加入，容斥计算即可。

设 f_S 表示已经考虑 S 集合的方案数，有转移

缩 2 度点：

• f = f_1f_2
• g = g_1g_2 + 2(f_1f_2 + f_1g_2 + g_1f_2)

复合重边：

• f = f_1f_2 + f_1g_2 + g_1f_2
• g = g_1g_2

应该都比较好理解，最终只需在预处理是提前处理一下贡献。

UOJ 集训队互测 2021 逛公园

总结

广义串并联图实则上就是通过，删 1 度点，缩 2 度点，复合重边这三种操作不断的缩小问题规模，直至范围变为我们容易解决的问题。本质上是一种化简问题的手段。

参考

广义串并联图方法学习笔记

IOI2019集训队论文 -《公园》命题报告