Matrix-Tree定理

Matrix-Tree定理是用于解决图的生成树计数的一个定理,复杂度在O(n^3)级别。

内容:

构造一个仅在主对角线有值的矩阵AA(i,i)的值为i号点的度数;

注意:这里的A(i,i)是出度,无向图算两次。

再构造一个邻接矩阵B

A-B得到一个基尔霍夫矩阵

我们取任意一个形如M(i,i)的该矩阵的代数余子式,其值就是以i为根的生成树的数目,在有向图中表现为i为根的树形图树目,无向图中就是生成树数目。

实现:

构造出基尔霍夫矩阵之后,取一个需要的代数余子式,类似高斯消元的求出它的上三角形式(左上到右下),这条主对角线上元素的乘积就是该行列式的值。

证明:

咕着。

细节:

1.在辗转相除消元的时候,交换行列式的行/列时符号要取反。

2.最后在模意义下ans可能是负数,要加一个mod

3.注意不要去消无用的点,比如对某个联通块求值的时候,那些不在该连通块里的点不要消。

4.行列式的运算法则和一般的矩阵消元不一样,若用行B消去行A,只能形如A-B*C,形如A*C-B是不合法的。

拓展:

1.求解有向图的树形图:度数矩阵定义为出度/入度,分别对应外向/内向。邻接矩阵单向,代数余子式为原矩阵消去根。

2.求解带权图的生成树边权乘积之和:度数矩阵为边权和,邻接矩阵为边权即可。

题目:

[SHOI2016]黑暗前的幻想乡

题目链接

题意:有n个点,一些边,每个边有一个颜色,共有n-1种颜色,求每种颜色边恰好出现一次的生成树的个数(n<=17)

solution:考虑容斥,设f[i]表示至多有n种颜色的生成树数量,g[i]表示恰好有n种颜色的数量。那么有g[n]=f[n]-f[n-1]+f[n-2]-f[n-3]...,求解f[i]可以使用矩阵树定理做到O(n^3)。因为要带个求逆元的log,于是总复杂度就是O(2^nn^3log(INF))

[SDOI2014]重建

题目链接

巧妙而神仙。

题意:每个边有一个出现概率,求出现的边恰好构成一颗生成树的概率。(n<=50)

solution:矩阵树定理其实求的是

\sum_{Tree}\prod_{e \in Tree}P_{e}

而平时这个P_{e}都是1,我们没有过多的管它。

此题要求的是

\sum_{Tree}\prod_{e \in Tree}P_{e}\prod_{e \notin Tree}(1-P_{e})

上面那个式子化一下

\sum_{Tree}\prod_{e \in Tree}P_{e} \frac{\prod_{e}(1-P_{e})}{\prod_{e \in Tree}(1-P_{e})}

\prod_{e}(1-P_{e})\sum_{Tree} \frac{\prod_{e \in Tree}P_{e}}{\prod_{e \in Tree}(1-P_{e})}

后面那个式子就可以上矩阵树定理了。

注意:前面那个式子每条边只能被算一次。

[UOJ]智商锁

题目链接

究极人类智慧题。

题意:构造点数为不超过100的图,使得模998244353意义下生成树个数为K

solution:随机化,按照出题人的题解,随机1000个点数为12的图,分别矩阵树定理算出生成树个数,复杂度O(1000*12^3),然后选4个块粘在一起,两个连通块间只有一条边,设生成树个数为f(G),那么这四个块粘在一起的生成树个数就是f(G_1)f(G2)f(G3)f(G4),O(1000^2)的算出答案存起来。再O(1000^2)的枚举另一半,每次O(1)查询另一半是否存在。

图的生成方式是保证图联通的前提下,其余每条边出现概率为0.8(只要保证图很随机即可)。

正确性:f(G)的取值范围是[0,12^{12-2}],这是远大于模数的,这样从1000个种选4个这么大的数乘起来就有约1000^4=1e12种取值,那么如果1e12个点随机撒下来能够覆盖住K就可以找到答案,算一波概率就是1-(1-\frac{1}{1e9})^{10^{12}},约等于1-\frac{1}{e^{1000}},这个概率几乎就是1

0%