一般图边覆盖计数
ღꦿ࿐
·
·
算法·理论
今天模拟赛中出现了一个题，需要对一个 n 个点，m 条边的图做边覆盖计数，边覆盖是一个边集 S\subseteq E 使得任意一个点 i 都存在一条边 (u,v)\in E 满足 u=i 或 v=i，即覆盖所有的点。
然后被我使用神秘做法冲过去了（然后莫名其妙登顶？）求叉 & 求证明。
这是一个 NPC 问题。
### 做法1(题解)
考虑类似 meet-in-the-middle 地将图划分成两块 $A,B$，分别求出 $f(S),S\subseteq A$ 和 $g(S),S\subseteq B$ 表示在 $A,B$ 的导出子图内选择若干边，覆盖点集 $S$ 的方案数，剩下需要考虑 $A-B$ 之间的边，令其有 $L$ 条，我们对 $2^{|L|}$ 地枚举所有选中间的边的方案，则会要求两侧有一些点必须被覆盖，
该算法的时间复杂度是 $O(2^{S}S+2^L)$，其中 $S=\max(|A|,|B|)$，直接随机大量划分 $A,B$ 的方案并计算该值，取复杂度最小的划分 $A,B$ 来进行计算，题解瞎几把证明了一通并声称能过。
一个能将本做法卡至相对较高复杂度的数据是两个相对着的菊花，形如 $(1,3),(2,3),(1,4),(2,4)\dots (1,n),(2,n)$，这个时候最优的划分是将 $1,2$ 划分至同一侧，剩下的点相对不平均地划分，要是平均地划分边会多达 $30$ 条，随机到一侧点集稍大可以使得边数处于可以接受的范围内，最终复杂度较有时可能会达到大概 $2^{26}$ 左右。
### 基于点的统计
考虑基于边的枚举复杂度太高，基于点地统计答案。
做容斥，枚举 $S$ 中的点，钦定 $S$ 中的点没有被覆盖，剩下的点集随便有没有被覆盖。
那么一些边被限制不能选中，其它边随意选，统计出端点均不在 $S$ 中的边的个数 $C(S)$，答案即 $\sum (-1)^{|S|}C(S)$，直接做即可做到 $O(2^n\times m)$。
后面两个做法均需要此容斥。
### 做法2(Yet Another Random Solution)
这是我赛时的做法。
考虑将点集划分成 $A,B$ 两坨，且大小分别为 $\lfloor n/2\rfloor ,\lceil n/2\rceil $，分别对 $A,B$ 导出子图内部进行上面的容斥，并枚举 $A,B$ 钦定的情况，再考虑中间的边，若两侧都没有被钦定则有 $2$ 的系数，否则一定不能选，只有 $1$，这样直接做是 $O(2^nm)$ 的，但是注意到我们完成了内部的容斥后只关心 $A$ 中与 $B$ 有边的点是否被钦定，称之为 $La$，同理还有 $B$ 中与 $A$ 有边的点集 $Rb$，我们统计 $La$ 中被钦定非法的点为 $SLa$ 的方案数，和 $Rb$ 中被钦定非法的方案数 $SLb$ 的方案数，然后仅枚举这两个集合的子集并考虑中间的边的系数。
时间复杂度 $O((2^{n/2}+2^{|La|+|Rb|})m)$。
同理，我们大量随机 $A,B$，取复杂度最小的来跑。
取 $Test = 10^6$，在大量随机数据及我尝试构造的数据下，在题目数据范围下 $|La|+|Rb|$ 的最值不会超过 $16$。
这玩意甚至能跑 $m\leq 75$，感觉比做法 1 快了很多，有没有人能讲讲证明/hack 阿。
一个能将本做法卡至相对较高复杂度的数据是两个相对着的菊花，形如 $(1,3),(2,3),(1,4),(2,4)\dots (1,n),(2,n)$，这个时候最优的划分是将 $1,2$ 划分至同一侧，剩下的点平均划分开，在本题的数据范围下最多有 $16$ 个点向另一侧有边，需要被考虑。
### 做法3(超级炫酷爆标确定性做法)
考虑上面容斥，每次枚举一个点并考虑是否钦定，若钦定则删去其周围的边，若不钦定则周围的边的答案仅依赖于连接的另一个点是否钦定，将边挂在它的另一侧即可。故考虑完这个点是否钦定后，我们可以直接删除掉这个点。
直接删除所有点仍然是 $O(2^n)$ 的，删除一些边缘的点是没啥用的，故我们不断删除度数不小于 $3$ 的点，最多删除 $m/3$ 次，接下来剩下的所有点度数不超过 $2$，故剩下的图是若干环和链（含孤点），这个东西的覆盖是简单的，直接断环为链，对链跑 dp，记录目前点是否钦定，需要乘上那些挂在上面的边的系数。
时间复杂度 $O(2^{m/3}(n+m))$，故本题的 $n$ 其实可以开到 $60$。