Matrix Tree定理+基尔霍夫矩阵求生成树计数--luoguP4111

本文主要是介绍Matrix Tree定理+基尔霍夫矩阵求生成树计数--luoguP4111，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含n*m个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。

你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案。

输入输出格式

输入格式：
第一行两个数分别表示n和m。

接下来n行，每行m个字符，每个字符都会是’.’或者’’，其中’.’代表房间，’’代表柱子。

输出格式：
一行一个整数，表示合法的方案数 Mod 10^9

输入输出样例

输入样例#1：复制
2 2
…
…
输出样例#1：复制
4
输入样例#2：复制
2 2
.
.
输出样例#2：复制
0
说明

对于前20%的数据，n,m <= 3

对于前50%的数据，n,m <=5

对于前100%的数据，n,m<=9

有40%的数据保证，min(n,m)<=3

有30%的数据保证，不存在柱子

基尔霍夫（Kirchhoff）矩阵树定理

给定一个有n个节点的简单图G，令它的拉普拉斯矩阵（Laplacian matrix）为Q，Q*的行列式即为图G的生成树的个数。
若图G为多图，矩阵Q做如下修改：
$当i ≠ j，令q_{i,j}等于m (m为i节点和j节点之间边的数量)。$
$当i = j，令q_{i,j}等于点i的度减去i的自环。$
简单图：无重边无自环的无向图。
$拉普拉斯矩阵：给定一个有 n 个节点的简单图 G ，它的拉普拉斯矩阵 L n * n 定义为：$

$L = D - A$

$其中 D 为度矩阵， A 为邻接矩阵。$
$度矩阵：给定图 G = (V, E) ， G 的度矩阵 D 定义为一个 n * n 的矩阵：$
$di,j=\begin{cases}deg(vi)& if\ i=j\\0&otherwise\end{cases}$

$其中 d e g (v i) 为节点 v i 边的数量。$
邻接矩阵：对于一个有n个节点的简单图，它的邻接矩阵是这样一个n*n的矩阵：当节点i和节点j之间有边相连时， $A_{i,j}$ 为1；否则为0。
多图：有自环，有重边的图。

则Matrix-Tree定理可描述为:图G的所有不同的生成数的个数等于其Krichhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对r(1<=r<=n)，将C[G]的第r行、第r列同时去掉后得到的新矩阵，用Cr[G]表示。

上代码：

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 200
using namespace std;
int n,m,cnt,head[maxn],us[maxn][maxn];
long long link[maxn][maxn];
char a[maxn];
const int mod=1e9;long long Matrix(int n)
{for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)link[i][j]=(link[i][j]+mod)%mod;long long ans=1,f=1;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){long long A=link[i][i],B=link[j][i];while(B){long long t=A/B;A%=B; swap(A,B);for(int k=i;k<=n;k++)link[i][k]=(link[i][k]-t*link[j][k]%mod+mod)%mod;for(int k=i;k<=n;k++) swap(link[i][k],link[j][k]);f=-f;}}if(!link[i][i]) return 0;ans=ans*link[i][i]%mod;}if(f==-1) ans=(mod-ans)%mod;return ans;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",a+1);for(int j=1;j<=m;j++){if(a[j]=='.') us[i][j]=++cnt;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(!us[i][j]) continue;if(us[i][j+1]) link[us[i][j]][us[i][j]]++,link[us[i][j]][us[i][j+1]]--;if(us[i+1][j]) link[us[i][j]][us[i][j]]++,link[us[i][j]][us[i+1][j]]--;if(us[i][j-1]) link[us[i][j]][us[i][j]]++,link[us[i][j]][us[i][j-1]]--;if(us[i-1][j]) link[us[i][j]][us[i][j]]++,link[us[i][j]][us[i-1][j]]--;}printf("%lld\n",Matrix(cnt-1));return 0;
}