广义串并联图,缩边
以下只讨论无向图。
- K4:\(4\) 个点 \(6\) 条边的完全图;
- 同胚:删去所有二度点(删去该点,并用一条边连接该点连接的两个点)后,两图同构;
对于一个图 \(G(V,E)\),若其不存在与 K4 同胚的子图,则称其为广义串并联图。
对于一个广义串并联图,可以通过以下三种操作将其缩为一个点:
- 删 \(1\) 度点:度数为 \(1\) 的点可以直接删去,不会影响图的其它部分;
- 删 \(2\) 度点:删去该点,并用一条边连接该点连接的两个点;
- 叠合重边:将两条重边叠合为 \(1\) 条;
在某些题目中,我们可以运用这一方法,将问题分解为 \(3\) 个子问题:
- 处理 \(1\) 度点 所连接的唯一一条边产生的贡献;
- 求出两条边串联起来的等效边;
- 求出两条边并联起来的等效边;
如果原图是广义串并联图,则直接缩边即可得到答案。其余情况,如果题目保证 \(m\le n+k\)(其中 \(k\) 很小),则直接缩边后剩下的图一定满足 \(n'\le 2k,\ m'\le 3k\)。
证明考虑三类缩边操作:
- 删 \(1\) 度点:
--m, --n
; - 删 \(2\) 度点:
--m, --n
; - 叠合重边:
--m
;
因此最终的图一定有 \(m'\le n'+k\);同时最终的图上一定不包含度数小于 \(3\) 的节点(都被删掉了),因此有 \(3n\le 2m\),联立解得 \(n\le 2k,m\le 3k\)。对于 \(k\) 较小的情况可以直接暴力搜索求解。
代码容易出现的错误
- 度数数组
deg[u]
和邻接表的大小edg[u].size()
一定要时刻保持匹配。 - 一个点(\(1\) 度点、\(2\) 度点)被删掉后,一定要将其
deg
标记为 \(0\),保证不会被删除第 \(2\) 次。
250218 模拟赛 T2 color
题意
给定一个 \(n\) 个点 \(m\) 条边的联通无向图,给图上每个点染上 \(k\) 种颜色中的一种,且要 求每一条边的两个端点不同色(不需要使用全部 \(k\) 种颜色),求方案数 \(\bmod 10^9+7\)。
\(n\le 10^5, m\le n+5\)
按照题解的说法,图的染色问题在多项式时间内不可解。注意到题目给定了一额外限制条件:\(m\le n+5\)。对于这种形式的约束条件,我们可以用广义串并联图的缩边方法,缩掉 \(1\) 度点和 \(2\) 度点,并叠合重边,最终会形成一个 \(n'\le 10,\ m'\le 15\) 的图,可以直接暴力求解。
虽然题目要求一条边的两个端点不同色;但缩边的过程中,两条边串联形成的等效边,两端点可以同色。
因此我们还需要考虑到这种情况。具体的,我们给每条边赋予两个权值:\(w_1,w_2\),分别表示两端点颜色相等、不等,等效边内部点染色的方案数(容易注意到边内部染色方案和两端点具体的颜色无关,只与其相等关系有关)。
考虑三类缩边操作:
- 缩 \(2\) 度点时考察中间点和两端点的颜色关系,即可得出转移;
- 缩 \(1\) 度点时直接将连边的 \(w_1+w_2\) 乘到答案的系数上;
- 叠合重边时直接将 \(w_1,w_2\) 对应相乘即可。
最终我们会得到一个 \(n'\le 10\) 的图,在上面暴力搜索每种本质不同的方案,统计其出现次数(\(\binom{k}{c}c!\))和等效边内部的贡献即可。
代码
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
|
P6790 [SNOI2020] 生成树
题意
给定一个图,保证该图由一个仙人掌添加一条边形成;问其生成树数量对 \(998244353\) 取模的结果。
\(n,m\le 2\times 10^5\);
注意到仙人掌添加一条边后,仍然是广义串并联图,可以缩为一个点。
考虑如何设置边的状态。生成树要求连通并且不能有环。一条等效边内部的节点只能通过等效边的两个端点连接到外部,因此每一个内部节点都至少连接到一个端点。
考虑串联:分讨中间点连接到哪个端点,并且是否同时连接。这需要我们记录每条等效边两端点 \(u,v\) 连通和不连通的方案数,分别记为 \(cc\) 和 \(cd\)。注意到并联和叠合重边时这两个属性也是容易转移的。直接做即可。