本文共 2124 字，大约阅读时间需要 7 分钟。
题意：n*m的字符矩阵，'.'代表卧室，'*'代表厨房。卧室与卧室之间有一扇门，要求任意两个卧室之间只有一条路。求路的总数。
题解：生成树计数模板题
无向图的基尔霍夫矩阵: 对角线上表示每个点的度数，若ij之间有边则矩阵ij处为-1。其他ij的值为0。
无向图的生成树的数目为: 任意一个n-1阶主子式的行列式的绝对值。（下面是模板）
1.模板题，这个可以转化为生成树计数，遇到求无向图的生成树个数，直接套用这个模板就ok。
#include#include #include #define MOD 1000000000using namespace std;int cnt = 0 ;int index[15][15] ;int row[4] = {0 , 0 , -1 , 1} ;int col[4] = {-1 , 1 , 0 , 0} ;bool A[105][105] ;long long B[105][105] ;long long det(int n) //计算n-1阶行列式 { int i , j , k ; long long t , ans = 1 ; for(i = 0 ; i < n ; i ++) { for(j = i + 1 ; j < n ; j ++) { while(B[j][i]) { t = B[i][i] / B[j][i]; for(k = i ; k < n ; k ++) { B[i][k] = (B[i][k] - B[j][k] * t % MOD + MOD) % MOD ; swap(B[i][k] , B[j][k]) ; } ans = -ans ; } } if(!B[i][i]) return 0; ans = ans * B[i][i] % MOD ; } return (ans + MOD) % MOD ; } int main(){ int i , j , k ; int n , m ; int begin , end ; long long ans ; int x , y ; char map1[15][15] ; scanf("%d%d", &n, &m) ; memset(index , -1 , sizeof(index)); memset(A , 0 , sizeof(A)); memset(B , 0 , sizeof(B)); for(i = 0 ; i < n ; i ++) scanf("%s" , map1[i]) ; for(i = 0 ; i < n ; i ++) for(j = 0 ; j < m ; j ++) if(map1[i][j] == '.') index[i][j] = cnt ++ ; for(i = 0 ; i < n ; i ++) for(j = 0 ; j < m ; j ++) { if(map1[i][j] == '*') continue ; for(k = 0 ; k < 4 ; k ++) { x = i + row[k] ; y = j + col[k] ; if(x < 0 || x >= n || y < 0 || y >= m) continue ; if(map1[x][y] == '*') continue ; begin = index[i][j] ; end = index[x][y] ; A[begin][end] = 1 ; } } for(i = 0 ; i < cnt ; i ++) for(j = 0 ; j < cnt ; j ++) if(i != j && A[i][j]) { B[i][i] ++ ; B[i][j] = -1 ; } ans = det(cnt - 1) ; printf("%lld\n", ans); return 0;}
转载地址：http://iiml.baihongyu.com/