转换题意后就是问你生成树的方案数
就是裸的矩阵树定理
不会证明，只懂结论：
对于一个无向图 G
定义G的度数矩阵 D[G] 是一个 n*n 的矩阵，并且满足：当 i ≠ j 时，d[i][j] = 0，当 i = j 时，d[i][j]等于 vi 的度数
定义G的邻接矩阵 A[G] 是一个 n*n 的矩阵，并且满足：如果 vi,vj 之间有边直接相连，则 a[i][j] = 1 否则为 0
定义G的 Kirchhoff 矩阵 C[G] 为 C[G] = D[G] - A[G]，则 Matrix-Tree定理可描述为：
G的所有不同的生成树的个数等于其 Kirchhoff 矩阵 C[G] 的任何一个 n-1 阶主子式的行列式的绝对值。
n-1 阶主子式就是将 C[G] 的第 r 行，第 r 列同时去掉后得到的的新矩阵（1 ≤ r ≤ n），用Cr[G]表示
行列式是什么不需要知道，只要知道怎么求
有下面的结论：
1.交换两行/列位置，行列式的值取相反数
2.用一行的倍数减去另一行，行列式的值不变
3.一个上三角行列式的值等于对角线的乘积
然后只要考虑如何把Cr[G]搞成上三角形式的矩阵
考虑高斯消元时的做法，把Cr[G]也用同样的方法搞成上三角形式
因为消元时有除法，而剩余系下没有除法，所以要用辗转相除法：
设当前位置值为 a ，然后我们要消掉另一行的 b
那么把 b 整行减去 （a 整行 * [b/a] ) [b/a]表示 b除a下取整
那么 (a,b) --> (a,b%a)
然后交换两行继续操作直到有一个为 0
注意每次交换后ans都要取相反数
计算矩阵行列式的代码如下：
//ans初始为1，A是矩阵 for(int j=1;j<=cnt;j++) { for(int i=j+1;i<=cnt;i++) while(A[i][j]) { long long t=A[j][j]/A[i][j]; for(int k=j;k<=cnt;k++) A[j][k]=(A[j][k]- t*A[i][k]%mo +mo)%mo, swap(A[i][k],A[j][k]); ans*=-1; } ans=ans*A[j][j]%mo; }
附上完整代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int mo=1e9; int n,m; char mp[17][17]; int A[107][107],a[17][17],cnt;//矩阵A就是Cr[G] long long ans=1; void slove() { cnt--;//把矩阵最外面一层去掉 for(int j=1;j<=cnt;j++) { for(int i=j+1;i<=cnt;i++) while(A[i][j])//辗转相除 { long long t=A[j][j]/A[i][j]; for(int k=j;k<=cnt;k++) A[j][k]=(A[j][k]- t*A[i][k]%mo +mo)%mo, swap(A[i][k],A[j][k]); ans*=-1; } ans=ans*A[j][j]%mo; } ans=(ans+mo)%mo; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",mp[i]+1); for(int i=0;i<=n+1;i++) mp[i][0]=mp[i][m+1]='*'; for(int i=0;i<=m+1;i++) mp[0][i]=mp[n+1][i]='*';//边界都是不通的 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]=='.') { a[i][j]=++cnt;//记录原图的位置对应的矩阵A中的位置 if(mp[i-1][j]=='.') A[ a[i][j] ][ a[i-1][j] ]=A[ a[i-1][j] ][ a[i][j] ]=1; if(mp[i][j-1]=='.') A[ a[i][j] ][ a[i][j-1] ]=A[ a[i][j-1] ][ a[i][j] ]=1; }//处理矩阵A for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) if(A[i][j]&&i!=j) A[i][i]++;//处理矩阵A slove(); printf("%lld",ans); return 0; }