TODO
前言
矩阵树定理的理解,且代码实现。并且添加了几道实战题目
简介&思路
Kirchhoff 矩阵树定理(简称矩阵树定理)解决了一张图的生成树个数计数问题。
无向图
设$G$是一个有n个顶点的无向图。定义度数矩阵$D(G)$为:
$D{ii}(G) = \mathrm{deg}(i), D{ij} = 0, i\neq j$
G的邻接矩阵$A(G)$为:
$A{ij}(G) = A{ij}(G)$
定义 Laplace 矩阵(亦称 Kirchhoff 矩阵)$L$为:
$L(G) = D(G) - A(G)$
$G$的所有不同的生成树的个数等于其Laplace
矩阵($L(G)$)的任何一个n-1
主子式的绝对值,所谓 n-1 阶主子式,就是对
于 r(1≤r≤n),将$G$的第 r 行、第 r 列同时去掉后得到的新矩阵$G_r$
举例:
无向图$G$如下图所示
则$A(G)$表示为:
$\begin{matrix}0 & 1 & 1 & 0\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\\end{matrix} $$D(G)$表示为:
$\begin{matrix}2 & 0 & 0 & 0\\ 0 & 3 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 1\\\end{matrix} $$L(G)$表示为:
$\begin{matrix}2 & -1 & -1 & 0\\ -1 & 3 & -1 & -1\\ -1 & -1 & 2 & 0\\0&-1&0&1\\ \end{matrix} $去除$r$ = 1之后得到主子式$G_r$的绝对值即为该图的生成树个数。
$G_r$ = $\begin{matrix} 3 & -1 & -1 \\-1&2&0\\-1&0&1\\ \end{matrix} $ 根据公式计算的 $|G_r|$ = 3
所以该图共有三种生成树。
![生成树个数.png](https://i.loli.net/2020/04/25/wkcxDdWRB3rvNPt.png)
生成树个数.png
是不是很神奇, 我也觉得很神奇,然后去看了证明,也很神奇😑
有向图同理
同理
行列式的变换
- 交换两行/列位置,行列式取相反数
- 对一行/列乘以某数,行列式也乘以某数
- 用一行的倍数减去另一行,行列式的值不变
- 一个上三角行列式的值等于对角线的乘积
- 转置矩阵,行列式不变
实现
按照数学公式计算余子式的值的话,复杂度达到$O(N!)*N $ ,所以需要通过行列式的性质,进行基础的变换之后再计算。
题目
小Z的房间
矩阵树定理的裸题,题目给定的限制为1≤n,m≤9
矩阵维度限制在了个位数,算法有待优化。
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 100;
const LL mod = 1e9;
int n, m, ed;
LL ans = 1;
int h[N][N], vis[N];
LL f[N][N];
char s[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
for (int j = 0; j < m; j++)
if (s[j] == '.')
h[i][j + 1] = 1; //记录下房间的位置
else
vis[(i - 1) * m + j + 1] = 1; //重要!!为墙的行一定全为0!!
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (h[i][j]) { //若为房间
ed = 0; //纪录度数矩阵
if (h[i][j - 1])
f[(i - 1) * m + j][(i - 1) * m + j - 1] = -1, ed++; //左
if (h[i][j + 1])
f[(i - 1) * m + j][(i - 1) * m + j + 1] = -1, ed++; //右
if (h[i - 1][j])
f[(i - 1) * m + j][(i - 2) * m + j] = -1, ed++; //上
if (h[i + 1][j])
f[(i - 1) * m + j][i * m + j] = -1, ed++; //下
f[(i - 1) * m + j][(i - 1) * m + j] = ed; //加上度数矩阵
}
}
n = n * m - 1; //删去最后一行最后一列,并计算行列式的大小
for (int i = 1; i <= n; i++)
if (!vis[i]) { //注意! 非墙的才继续
for (int j = i + 1; j <= n; j++)
if (!vis[j]) //同上
while (f[j][i]) { //辗转相除
LL r = f[i][i] / f[j][i];
for (int k = 1; k <= n; k++)
f[i][k] = (f[i][k] - f[j][k] * r % mod + mod) % mod, swap(f[i][k], f[j][k]);
ans = (mod - ans) % mod; //交换两行,答案取负
}
if (f[i][i] == 0) {
puts("0");
return 0;
} //若主对角线有0,则答案为0
ans = (ans * f[i][i] + mod) % mod; //计算答案
}
printf("%lld\n", ans);
}
一下是测试结果
![矩阵树定理-小Z的房间.png](https://i.loli.net/2020/04/25/83mHkVnXCqbGpOW.png)
矩阵树定理-小Z的房间.png
轮状病毒
总结
引用周东老师的结束语吧:
扎实的数学功底是解决问题的保证,创造性地联想是解决问题的灵魂。