图论状压

· · 个人记录

一般图连通性

[ABC213G] Connectivity 2

题目链接

设 f_S 表示只考虑 S 集合中的点，联通方案数。转移时可以通过容斥，枚举与 1 联通的一个联通块，并强制剩余的点不与其联通，预处理后 O(3^n)。

边双联通分量

[SNOI2013] Quare

题目链接

我们通过耳分解将变双划分为若干个耳，设 f_S 表示 S 集合满足边双的最小权值，g_{S,i,j} 表示这个耳包含元素集合为 S，从 i 出发现在在 j 的最小权值。这样是 O(3^nn) 的。可以维护构成耳的中间过程，设 g_{S,i,j} 表示加入了集合 S，当前的耳到了 i，最终目标为 j 的最小权值。这样转移是 O(2^nn^3)。

[CF1155F] Delivery Oligopoly

题目链接

和上面一道题做法相似。仍然使用耳分解进行 \text{dp}，维护最小边数，状态也是一样的。

仙人掌

[2019 ptz Summer] Counting Cactus

题目链接

与对树的拆分相似，我们定义 f_{S,i} 表示以 i 为根，仙人掌集合为 S 的方案数。每一次尝试向其中加入一个子仙人掌，或加入一个包含 i 的环（环上的点可能挂了子仙人掌）。这样再定义 g_{S,i,j} 表示一条集合为 S，两端点分别为 i,j 的链的方案数。

会发现有两处算重，一个是环上会正反遍历两遍，还有重边的时候同一个子仙人掌在 f,g 会重复统计贡献，在中途将贡献 /2 则刚好不重不漏。时间复杂度 O(3^nn^3)。

DAG

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

题目链接

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

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

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

f_S = \sum_{T \sube S} (-1)^{|T|-1} f_{S \bigoplus T} g_T 将容斥系数塞入 $g_T$ 里面，子集卷积可以做到更优。 ## 强连通 ### [Grand Prix of Korea] Economic One-way Roads [题目链接](https://codeforces.com/gym/102759/problem/C) 同样可以采用耳分解方法状压，与边双几乎完全一样的状态设计。注意重边处的处理。一种较为方便的方法是钦定开始所选择的时较小边。 ### [清华集训 2014] 主旋律 [题目链接](https://uoj.ac/problem/37) 如果继续采用上面的计算方法，很明显会算重，此外钦定加入顺序也行不通。 设 $f_S$ 表示只考虑 $S$ 中点的生成子图的强连通方案数。如何转移呢？我们考虑容斥，减去所有的不合法方案。不合法的方案有什么性质呢？它一定由多个强连通分量构成，缩点后可以视为一个 $\text{DAG}$。所以我们可以枚举那些入度为 $0$ 的强连通分量，然后可以采用上面 $\text{DAG}$ 的方法容斥，即再定义 $g_S$ 表示 $S$ 集合中形成若干个无出度强连通分量，考虑上容斥系数 $(-1)^{强连通分量个数+1}$ 的方案数。设 $E(S, T)$ 表示 $S$ 向 $T$ 连边数量。那么有以下转移： - $f_S = 2^{E(S,S)} - \sum_{T \sube S, T \not= S} 2^{E(S \bigoplus T,S \bigoplus T)+E(T,S \bigoplus T)} \times g_T

求解 g 时需要枚举标号最小的块以免算重，g 中带容斥系数是因为一个 S 可能会被划分成多次加入。此外要注意 f,g 之间的更新顺序。

集合幂级数优化

大多题目可以在上面找到来源。

一般图联通子图个数

设 F(x) 表示生成联通子图的形式幂级数，G(x) 表示生成子图的形式幂级数。定义乘法运算为子集卷积，那么可以列出

G(x) = e^{F(x)} - 1

由于求解 G(x) 是平凡的，可以形式幂级数求 \text{ln} 得到 F(x)。

时间复杂度 O(2^nn^2)。

点双连通生成子图计数

题目链接

首先我们可以求出生成联通子图的形式幂级数，但我们要满足点双的限制，即删除任意一个点后图仍然联通。在形式幂级数中，删除第 i 个点后的生成子图进行 \text{ln} 操作即为删除 i 后仍然联通的生成联通子图的形式幂级数。这样我们可以一次遍历 1 \sim n，假设当前遍历到 i，我们已经求出了删除 1 \sim i - 1 中任意一个点后仍然为连通子图的形式幂级数。此时我们只需要将包含点 i 相关的位置取出，将这部分首先变为 \text{exp}，并钦定 i 不在其中，求出删除 i 后仍然联通子图的形式幂级数后再 \text{ln} 回来。

时间复杂度 O(2^nn^3)。

边双连通生成子图计数

题目链接

边双无法像点双一样逐边考虑。考虑其与点双计数的不同之处。当总点数 \ge 3 时，一个满足点双的生成子图图一定满足边双，\le 2 的一定不为边双，但存在割点时也可能是边双。我们还是依次对 i 考虑，删除它不为割点的限制。当处理到 i 时，可以删除 i，考虑其中的每一个子联通块（包含点 i）要满足是一个边双，这些子联通块可以子集卷积合并，所以再倒着做一遍 \text{exp} 即可。

时间复杂度 O(2^nn^3)。

仙人掌生成子图计数

题目链接

一个仙人掌可以视为若干个长度 \ge 2 的环拼在一起。我们可以求出环的形式幂级数，每一次合并环时考虑这些环的交点 i，就是去掉 i 之后做一遍 \text{exp}，与上面较为相似。求环的形式幂级数可以直接状压

时间复杂度 $O(2^nn^3)$。 ## 参考 [集合幂级数的ln, exp](https://www.cnblogs.com/chasedeath/p/13891189.html) [一类图论相关的状压 DP 题的常见解法 ](https://www.cnblogs.com/Mackerel-Pike/p/16395436.html)