图计数

未分类

矩阵树定理

记号

度数矩阵是说每个点所连边的边权和，邻接矩阵就是边权。

公式

参见OI Wiki

求的是什么

每棵带标号生成树的边权乘积之和。

怎么求

1. 交换行，矩阵行列式值取负；
2. 一行减去另一行 $k$ 倍，行列式值不变；
3. 上三角矩阵的行列式值等于主对角线乘积。

高斯消元即可。

例题

1.[ZR-WC]图

给定一个 $n$ 个点 $m$ 条边的简单图$G=(V,E)$，定义一个图是好图当且仅当它至多有一个连通块是环套树，而其余连通块都是树，定义一个好图的价值为它的所有连通块大小的乘积，求 $\sum_{E'\in E,G'是好图}val(G'(V,E'))$。
$n\le 16$

考虑简化情况：好图定义为所有连通块都是树。那么这是一个套路，连通块大小乘积的组合意义为为森林里每棵树指定一个根的方案数。建一个虚点 $0$ 号点，把它与所有点连边生成辅助图 $G'$，发现 $G$ 的价值等于 $G'$的带标号生成树数量，可以上矩阵树定理。
考虑原问题。直接枚举环，缩点后就跟简化情况一样了。相同点集的环可能有多种组成情况。我们枚举环上标号最大的点 $x$，设 $f_{i,S}$,表示起点为 $x$ 经过点集 $S$，终点为 $i$ 的简单路径数，要求 $\forall y\in S,y\le x$ ，则以 $x$ 为最大标号的环的数量为 $\sum f_{x,S}/2$。$f$ 很好 $DP$。

2. 夕张的改造

见[省选模拟]6.12