【讲课】12.8集训讲课

学军集训讲课第三天。


CF468E Permanent

有一个 n×nn\times n 的矩阵 AA,除了给定的 kk 个位置以外的位置值都为 11

求该矩阵的积和式 prem(A)\operatorname{prem}(A)

prem(A)=σSni=1nai,σi\operatorname{prem}(A)=\sum_{\sigma\in S_n}{\prod_{i=1}^{n}{a_{i,\sigma_i}}}

n105,k50n\leqslant10^5,k\leqslant50

题解

prem(A)=σSni=1n(ai,σi1)+1\operatorname{prem}(A)=\sum_{\sigma\in S_n}{\prod_{i=1}^{n}{(a_{i,\sigma_i}-1)+1}}

将行列拆开看作二分图,第 ii 行与第 jj 列间边的权值为 ai,j1a_{i,j}-1(为 00 则没有边)。

f(i)f(i)ii 个匹配的匹配边的乘积的和,则答案为 i=0n(ni)!f(i)\sum_{i=0}^{n}{(n-i)!f(i)}

对于不连通的情况分连通块计算最后合并。

计算一个连通块的 ff 值有两个做法:设 ss 为连通块点数,tt 为连通块边数

  1. 由于图为二分图,必有一边的点数小于 s2\dfrac s2,于是对点数少的一边做状压dp,时间复杂度 O(2s/2t)O(2^{s/2}t)

  2. 随意找一棵生成树,枚举非树边是否选择,再在树上做树形dp,时间复杂度 O(2ts+1s2)O(2^{t-s+1}s^2)

综上,计算 ff 值的时间复杂度为 O(min(2s/2t,2ts+1s2))O(\min(2^{s/2}t,2^{t-s+1}s^2))

总时间复杂度 O(k22k/3)O(k^22^{k/3})

最大团(MCP)

给出一张 nn 个点 mm 条边的简单图,求最大团。

n,m200n,m\leqslant200

题解

算法一

定义度数小于 BB 的点为小点,其余点为大点。

O(22m/B+2BmB)O(2^{2m/B}+\frac{2^Bm}{B})

B2mB\sim\sqrt{2m} 时最优,时间复杂度为 O(m22m)O(\sqrt{m}\cdot2^{\sqrt{2m}})

算法二

最大团等于补图的最大独立集。

f(V)f(V) 为点集 VV 的最大独立集的大小。

直接搜索,枚举一个点 xx 考虑是否选取它,有:

f(V)=max{f(Vx),1+f(VxN(x))}f(V)=\max\{f(V-x),1+f(V-x-N(x))\}

按照度数从大到小枚举点,由于新图是稀疏图的补图,这个搜索会跑得特别地快(讲题人原话)。


目前学术界解决 nn 个点的图的最大独立集问题的时间复杂度一般认为是 O(1.1892n)=O(2n/4)O(1.1892^n)=O(2^{n/4})