一类图上的状压 dp 与连通性问题

Showmetheflower · 2025-09-13 09:44:56 · 算法·理论

一类图上的状压 dp 与连通性问题

简要的概述一下大纲：

子集反演（用在 dag 计数里）

形态/连通性刻画方式

例题

前置-子集反演

完全可以跳过。

令 f_S 表示恰好满足限制集 S 下的答案，g_S 表示至多满足限制集 S 下的答案。（满足 S 的一些，但是不能满足 S 之外的）。

我们对此有结论：

f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}g_T

推导：

首先有 g_S=\sum_{T \subseteq S}f_T。

f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}g_T=\sum_{T \subseteq S}(-1)^{|S|-|T|}\sum_{Q \subseteq T \subseteq S} f_Q=\sum_{Q \subseteq S} f_Q\sum_{Q \subseteq T \subseteq S} (-1)^{|S|-|T|}=\sum_{Q \subseteq S} f_Q\sum_{T \subseteq S-Q} (-1)^{|S|-|Q|-|T|}=\sum_{Q \subseteq S}f_Qh_{S-Q}

令 h_S=\sum_{T \subseteq S} (-1)^{|S|-|T|}=\sum_{i=0}^{|S|} C(|S|,i)(-1)^{|S|-i}=[S=\emptyset]。

故 \sum_{Q \subseteq S}f_Qh_{S-Q}=f_S，即式子成立。

同理如果令 g_S 表示至少满足限制集 S 的答案。（可以满足其它的，但 S 内的限制必须满足）

我们有类似的：

f_S=\sum_{S \subseteq T} (-1)^{|T|-|S|}g_T

如何证明？我们把上面的 g 取补集即可得到。

P6442

给定 n 个全集（长度为 m）的子集，求选出一些子集使得并为全集的方案数。
n \leq 10^6,m \leq 20

我们需要求恰好是全集的方案数，子集反演变成求每个子集的 “至少”，令当前要计算的集合为 T。那么就是要求最后的并是 T 的子集的方案数。相当于选择的每个子集都是 T 的子集，因此直接 sosdp 统计一下每个 T 子集内有多少个给定的集合即可。

P3349

给定一个树和一张图，求排列 P 的数量满足对于树上一条边 (x,y) 在图上都有对应的 (P_x,P_y)。
n \leq 17,m \leq \frac{n(n-1)}{2}

转完以后对于一个 T，是要求所有的 P_i \in T 时的答案，我们令 f_{i,j} 表示 P_i=j 的情况下子树内的答案。转移是朴素的。

形态的刻画

对于一些对图的形态或者连通性有限制有限制的问题，一般没法刻画。接下来有一些经典的处理方式，一般为构造或者规约。构造一般会出现构造到同一个方案的情况，不能用在计数问题里。这里的构造一般采用增量。而介绍的规约的方法一般都是可以做到只计算一次或者可容斥的。

如何做增量呢？其实就是耳分解。什么，你问我怎么证明？我太菜了不清楚 qwq。

朴素的

树：

规约：

每次删掉叶子，剩下还是一棵树。

同时你也可以考虑对于树的根，拆掉以后剩下的是若干个子树，依旧保留有树结构。

增量：每次对于每个叶子考虑接一些新的点。

DAG：

增量：每次在原有的一个 DAG 上，新拿出来一些点，并和原图的入度为 0 的点连一些指向这些 0 度点的边，重复这个过程（其实在实际运用的时候我们只需要扩展一步）。

规约：把入度为 0 的点从一个 DAG 中删掉（删除点以及相连的边），剩下的图还是一个 DAG。

更加困难的

强连通

增量：

对于原有的强连通的图，选择一对 (u,v) 添加一条 u 到 v 的路径，同样每次只需要扩展一步。初始状态是一个孤点。

规约：

考虑容斥一步，统计不强连通，等价于缩点后是数量大于 1 的极大 scc 组成的 DAG，我们用类似处理 DAG 的手法解决。

前情提要：

一个图点双连通，那么可以划分成一个闭耳拼上一些开耳。 一个图边双连通，那么可以划分成一个闭耳拼上一些开/闭耳。

注：下面的 u 表示路径的起点，v 表示路径的终点。

边双：

增量：

在原有的点双上加一个路径，且中间经过的点必须是原有的图外面的点。这里不要求 u \neq v 因为不限制是否是开耳。初始状态是一个闭耳。（一个环）

规约：

考虑容斥一步，变成不边双连通。此时缩点（e-dcc 缩点）后是一棵边双树，那么我们可以类比 dag 的方法枚举叶子（这里你得限制不是全集）。当然你得考虑一条边连着两个点的情况，这种就全是叶子得考虑进答案里。

点双：

增量：

在原有的点双上加一个路径，要求起点 u 不等于终点 v，且中间经过的点必须是原有的图外面的点（其实就是一个开耳）。初始状态是一个闭耳。（一个环）。

规约：

依旧考虑容斥。可以考虑 v-dcc 缩点或者圆方树来刻画这个东西，这样就能用树的方法做了。

例题

DAG

我们令 f_S 表示点集 S 内部的点和边组成的图为 DAG 的方案数，那么在转移的时候，我们可以枚举入度为 0 的点（设这个零点集合为 T），那么将这些点以及它们相邻的边删除后，剩下的图应该是还是个 DAG，这样可以规约到子问题：f_S=\sum_{T \subseteq S且T非空}f_{S-T} \times ...。但这是不对的，因为这里你钦定了一些点是 0 点，意味着一种方.案3在很多种钦定 0 点的选择中会被计算，因此我们想算的恰好满足某些点是 0 点的答案，因此使用子集反演可以得到：f_S=\sum_{T \subseteq S且T非空}(-1)^{|T|+1}f_{S-T} \times ...。

其实树也是基本一致的，将 T 定为叶子即可。

推导的话是不难的，注意到我们可以算 g 也就是至少集合 T 为零点的方案数，那么对于每个 T 其实我们想求的是 f 也就是恰好，那么把 f 表示成 g，然后对于每个 g 算系数旧可以得到上面的那个东西。

bzoj2863

求 n 个点的有标号 DAG 数量。
n \leq 10^3

板子题。令 f_n 表示 n 个点的答案，每次转移枚举入度为 0 的点的个数即可。

P6846

给定一个 n 个点 m 条边的有向图，你可以对每条边选择翻转方向（不能次数>1），求使得图变成 DAG 的所有操作方案中操作边数之和。
n \leq 18,m \leq \frac{n(n-1)}{2}

注意到对于一个合法的方案，我们对于把所有边方向取反一下，还是个 DAG 也是一种方案，并且注意到这样的一对方案操作的边数和为 m 。于是两两配对之后可以得到答案：ans=\frac{m \times c}{2}，其中 c 为方案数。

于是就是套路了，令 f_S 表示集合内的答案，每次枚举零点的集合 T，其中 T 要满足内部没有边，因为只要有边必定存在入度。

AT_abc306_h

有 n 个数 A_1,A_2,\dots,A_n，有 m 条限制形如 A_x ? A_y，其中 ? 可以填成 <,=,> 中的一个。问有多少种填的方法使得没有逻辑上的矛盾？

我们把一个关系看成一条无向边。

如果没有 = 的话相当于给每个边定向使得图是个 DAG，做法和上一个题一致。现在有 = 话意味着我们对于上一个题枚举的 T 不用要求 T 内没有边了，我们可以把内部连通的点缩起来（其实就是内部的边全填等于），容斥系数和入度为 0 的点个数相关，这里就是 T 内缩点完的个数，用并查集维护即可。

强连通

Gym102759C

给定一张无向图和将其上每条边定向的代价，求使图强连通的代价最小的定向方法。

考虑增量。

那么思考一下，每次增加一条路径相当于加入一些新的点，使得现在加入的所有点强连通。注意到只关注连通性，所以我们设 f_S 表示使得 S 连通的最小代价，那么每次转移就要枚举一个路径。但是这个路径似乎是有 2^{n-2}|S|^2 的，但是注意到如果我们只用枚举中间点都是新的的路径（考虑对于一个中间有旧点的路径你可以拆掉）。

还有个小问题就是你有可能有一些边没有考虑到（你选了一些使得强连通了，但是剩下的没考虑到，然而这些边虽然对连通性没有影响，但你还是得考虑的），于是我们先把每个边 (u,v) 定向到 \mathrm{min}(G_{u,v},G_{v,u}) 那一方，然后对于选择路径上的边算一下新增的贡献即可。

于是现在有一个复杂度 O(3^nn^2) 的做法。

考虑针对这个路径来处理，额外加一个 g_{S,u,v,0/1} 表示：假设原有的连通集合为 S' ，现在有一个从其中的一个点出发来扩展一条路径，这条路径现在走到 u，预期的终点为 v，当前是否可以连接 (u,v) 的情况下，满足 S' 和现在到 u 的路径的并为 S 的最小代价。

我们思考一个路径是如何产生的，显然是先选一个初始点，然后扩展一个初始边，然后每次不停往外扩展一个边，然后再选一个点结束。

于是那么我们考虑两个问题：

1. g 的自我转移？（扩展一个边）

f 对 g 的影响？（扩展一个初始边）

g 对 f 的影响？（结束）

1. 自我转移 考虑扩展路径，找下一个。考虑对于 g_{S,u,v,0/1} 可以转移向哪些 g 呢（这里 0/1 不限因为不会直接连到 v）？显然是枚举 w 为 u 下一个节点，即有转移 g_{S,u,v,0/1}+G_{u,w} \to g_{S \cup w,w,v,1}。 2. f 对 g 的影响 对于 f_S，考虑枚举 (u,v) 和 u 出发的第一个后继点 w，有转移 f_S+G_{u,w} \to g_{S \cup w,w,v,[u \neq v]}，其中 [u \neq v] 是因为如果 u=v 的话，就不能直接 u \to w \to v 这样自己连出去再连回来。 3. g 对 f 的影响 考虑对于 g_{S,u,v,1}（最后一维要求是 1 因为要直接到 v），这个没啥好说的，直接把路径拼上 u \to v 的边即可，g_{S,u,v,1}+G_{u,v} \to f_S。

于是就做完了。

主要代码：

int all = (1<<N) - 1;
memset(f, 0x3f, sizeof f);
memset(dp, 0x3f, sizeof dp);
f[1] = 0;
for (int S = 1; S <= all; S ++ ) {
    for (int u = 0; u < N; u ++ )
        for (int v = 0; v < N; v ++ )
            for (int b = 0; b <= 1; b ++ ) {
                if (dp[S][u][v][b] > lim) continue;
                for (int T = all ^ S; T; T &= T - 1) {
                    int w = __builtin_ctz(T);
                    if (G[u][w] >= 0)
                        Upt (dp[S | ( 1 << w )][w][v][1], dp[S][u][v][b] + G[u][w]);
                }
                if (b && G[u][v] >= 0)
                    Upt(f[S], dp[S][u][v][b] + G[u][v]);
            }
    for (int u = 0; u < N; u ++ ) if (S >> u & 1)
        for (int v = 0; v < N; v ++ ) if (S >> v & 1)
            for(int w = 0; w < N; w ++ ) if (!(S >> w & 1)) {
                if (G[u][w] < 0) continue;
                Upt(dp[S | ( 1 << w )][w][v][u != v], f[S] + G[u][w]);
            }
}

uoj37

给定一个 n 个点 m 条边的有向图，要求删掉一些边使得图强连通。
n \leq 15,m \leq \frac{n(n-1)}{2}

考虑令 f_S 表示集合 S 内部的图（点和内部边组成）强连通的方案数，考虑正难则反，转化为统计不强连通的方案数。不强连通等价于缩点（缩成若干个极大 scc）后是个 DAG，且点数 >1。

于是根据经典套路我们枚举所有入度为 0 的极大 scc 中的点组成的集合，令它为 T。那么我们记 g_T 表示 T 内点（就只考虑内部的边）划分为若干入度为 0 的 scc 的方案数。我们可以得到 f_S=\sum g[T]*(-1)^{P+1}*2^{edge(T,S-T)+edge(S-T,S-T)}，(-1)^{P+1} 是对应的系数，其中 P 为 T 中的 scc 个数。

对后面 2^{...} 的那个东西的说明：edge(T,S-T)+edge(S-T,S-T)：T \to S-T 中的边不影响是否是 DAG 的形态，S-T \to S-T 的边因为 T 中已经有个 scc，那么剩下就算只缩成一个，那么点数还是>1（因为你考虑如果=1那么相当于 T 这个集合分成的零度 scc 只有 1 个并且和 S-T 并成一个 scc，那么至少需要有一个 S-T \to T 的边，但显然因为零度点的定义，所以是不可能的），因此S-T内部的边随便连，S-T \to T的边是全都要砍掉的，因为入度为 0。

这个不能直接定量。考虑到系数只跟 P 的奇偶性有关，所以我们可以把 g_T 定义为奇数个 scc 的方案数 - 偶数个 scc 的方案数。

所以现在就是要求 g_T，考虑转移。如果单独一个 scc，就是 dp_S，否则考虑枚举 lowbit(S) 所在的 scc，那么得到 g_T=dp_T-sum(g[S - T'] \times dp_{T'})，其中 T' 为 lowbit(T) 所在连通块。这样就做完了。当然有一个细节就是在 f_S 的转移的时候，T=S 的时候你不能把 dp_S(dp_T) 也减掉，因为这个时候你不能把整个划分成一个 scc，这个是合法的。

主要代码：

const int N = 15, mod = 1e9 + 7;
int n, m, in[N], out[N], l[1 << N], p[1 << N], q[1 << N], f[1 << N], g[1 << N], pw2[N * N + 1];
int count(int x) { int res = 0; while (x > 0) res += 1, x -= x & (-x); return res; }
int lowbit(int x) { return x & (-x); }
void solve() {
    cin >> n >> m;
    pw2[0] = 1; rep(i, 1, n * n) pw2[i] = 2ll * pw2[i - 1] % mod;
    rep(i, 0, n - 1) l[1 << i] = i;
    rep(i, 1, m) {
        int u, v; cin >> u >> v;
        u -= 1, v -= 1;
        in[v] |= (1 << u), out[u] |= (1 << v);
    }
    rep(i, 1, (1 << n) - 1) p[i] = p[i & (i - 1)] + count(i & in[l[lowbit(i)]]) + count(i & out[l[lowbit(i)]]);
    rep(i, 1, (1 << n) - 1) {
        for (int j = (i - 1) & i; j; j = (j - 1) & i) q[j] = q[j + lowbit(i ^ j)] + count(j & in[l[lowbit(i ^ j)]]) - count((i ^ j) & out[l[lowbit(i ^ j)]]);
        for (int j = (i - 1) & i; j; j = (j - 1) & i) if (j & lowbit(i)) g[i] = (1ll * g[i] - 1ll * f[j] * g[i ^ j] % mod + mod) % mod;
        f[i] = pw2[p[i]];
        for (int j = i; j; j = (j - 1) & i) f[i] = (1ll * f[i] - 1ll * g[j] * pw2[p[i ^ j] + q[j]] % mod + mod) % mod;
        g[i] = (1ll * g[i] + f[i]) % mod;
    }
    cout << f[(1 << n) - 1] << '\n';
}

边/点双连通

CF1155F

给一张无向图，保留最少的边，使得图边双连通。

板子题，做增量。

注意到我们只关心现在哪些点连通，于是我们考虑令 f_S 表示使得 S 边双连通的最小保留边数，每次暴力枚举扩展一条路径即可。

细节方面的话，因为边双是闭耳加上一些开/闭耳，这个限制是很简单的，所以我们对每个点 u 的 f_{2^u} \to 0 然后每次加路径就不限制 u,v 是否相等即可。至于这个路径如何求呢？加一个 g_{u,v,S} 表示 u \to v 的路径，路径上的点集合为 T 的路径最小长度，求解 g 我们直接对每个点出发 dfs 一下即可。

HDU4997

给一张图，问有多少种加边的方法，使得图是边双。

板子题，容斥一下，然后做法和 uoj37主旋律 就基本一样了。

cpp

这个代码不是自己写的，网上找的。