题目链接：http://cogs.pro:8080/cogs/problem/problem.php?pid=1972
题解：
就是一道matrix-tree定理的模板题。（不熟悉该定理的同学请戳这里）
参考代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define LL long long 7 #define RI register int 8 using namespace std; 9 const int INF = 0x7ffffff ; 10 const int N = 110 + 2 ; 11 const int KI = 1e9 ; 12 const int cx[] = {-1,0,0,1} ; 13 const int cy[] = {0,1,-1,0} ; 14 15 inline int read() { 16 int k = 0 , f = 1 ; char c = getchar() ; 17 for( ; !isdigit(c) ; c = getchar()) 18 if(c == '-') f = -1 ; 19 for( ; isdigit(c) ; c = getchar()) 20 k = k*10 + c-'0' ; 21 return k*f ; 22 } 23 int n, m, tot = 0 ; LL bel[N][N], hh[N][N] ; char s[N] ; 24 25 inline LL det(int n) { 26 LL ans = 1, f = 1 ; 27 for(int i=1;i<=n;i++) { 28 for(int j=1;j<=n;j++) { 29 hh[i][j] = (hh[i][j]+KI) % KI ; 30 } 31 } 32 for(int i=1;i<=n;i++) { 33 for(int j=i+1;j<=n;j++) { 34 LL A = hh[i][i], B = hh[j][i] ; 35 while(B) { // 辗转相除高斯消元 36 LL t = A/B ; A %= B ; swap(A,B) ; 37 for(int k=i;k<=n;k++) hh[i][k] = (hh[i][k] - hh[j][k]*t % KI + KI)%KI ; 38 // for(int k=i;k<=n;k++) hh[i][k] = (hh[i][k] - hh[j][k]*t)%KI ; 39 for(int k=i;k<=n;k++) swap(hh[i][k],hh[j][k]) ; 40 f *= -1 ; // 每交换一次行列式就要改变符号 41 } 42 } 43 if(!hh[i][i]) return 0 ; 44 ans = ans*hh[i][i]%KI ; 45 } 46 if(f == -1) ans = (KI-ans) % KI ; 47 return ans ; 48 } 49 50 int main() { 51 // freopen("room.in","r",stdin) ; 52 // freopen("room.out","w",stdout) ; 53 n = read(), m = read() ; 54 for(int i=1;i<=n;i++) { 55 scanf("%s",s+1) ; 56 for(int j=1;j<=m;j++) { 57 if(s[j] == '.') { 58 bel[i][j] = ++tot ; 59 } 60 } 61 } 62 for(int i=1;i<=n;i++) { 63 for(int j=1;j<=m;j++) { 64 if(bel[i][j]) { 65 for(int k=0;k<4;k++) { 66 int x = i+cx[k], y = j+cy[k] ; 67 if(bel[x][y]) { 68 hh[bel[i][j]][bel[x][y]] -- ; // 度数矩阵-邻接矩阵 69 hh[bel[i][j]][bel[i][j]] ++ ; 70 } 71 } 72 } 73 } 74 } 75 printf("%lld",det(tot-1)) ; // 求取掉第n行和第n列的矩阵的行列式 76 return 0 ; 77 }