今天模拟赛中出现了一个题,需要对一个 \(n\) 个点,\(m\) 条边的图做边覆盖计数,边覆盖是一个边集 \(S\subseteq E\) 使得任意一个点 \(i\) 都存在一条边 \((u,v)\in E\) 满足 \(u=i\) 或 \(v=i\),即覆盖所有的点。
\(n\leq 40,m\leq 60\),1s 512M。
然后被我使用神秘做法冲过去了(然后莫名其妙登顶?)求叉 & 求证明。
这是一个 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\)。
标签:从洛谷,钦定,边覆盖,点集,计数,划分,枚举,做法,复杂度 From: https://www.cnblogs.com/Dreamerkk/p/18240467