kuangbin专题八 URAL1627 Join（生成树计数）

本文主要是介绍kuangbin专题八 URAL1627 Join（生成树计数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给出一个图,’.’表示卧室,’*’表示储藏间,每个格子上下左右都有一堵墙,然后需要打通一些卧室的墙（只能是相邻房间才能打通）使得卧室之间联通的方案数.
给每个卧室编个号,给可以打通的卧室加边,就是裸的生成树计数了.
题解：
打通一些卧室的墙之后，卧室之间就会变成一棵树，那么我们只要计算生成树的方案数就好了，怎么做呢，给每个卧室编个号,然后就是计算他们的联通边，写出邻接矩阵，然后弄个生成树计算模板就可以算出来结果了。
题外话：
ORZ，晚上和第二天早上一直超时和WA就是不知道为什么错误了，看了几个博客我看了都是差不多的啊，为什么超时了，为什么错了，最后改者改着发现了很多小问题，比如为什么超时呢？这道题的超时可能是因为你没弄long long int ,还有就是你的点数问题，不能只是10*10的矩阵，应该是100*100的矩阵，因为你原本的图最多可以有81个’.’也就是说最多有81个点，那么你如何是10*10的矩阵就算不出结果了，导致各种错误，还有最倒霉的就是我TM之前用的模板是错的！麻痹只能过一些题，还好做的这道题让我知道我的模板是错误的，不然就TM尴尬了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL long long int
const int MAXN=111;
const LL mod=1e9;
char s[MAXN][MAXN];
int map[MAXN][MAXN];
LL B[MAXN][MAXN];
int g[4][2]={1,0,-1,0,0,1,0,-1};
int id[MAXN][MAXN];
int tol;
LL determinant(int n)
{LL res=1;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){while(B[j][i]){LL t=B[i][i]/B[j][i];for(int 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]);}res=-res;}}if(!B[i][i])    return 0;res=res*B[i][i]%mod;}return (res+mod)%mod;
} 
int main()
{int n,m;while(~scanf("%d%d",&n,&m)){tol=0;memset(id,0,sizeof(id));memset(B,0,sizeof(B));for(int i=0;i<n;i++){scanf("%s",&s[i]);for(int j=0;j<m;j++)if(s[i][j]=='.')id[i][j]=tol++;}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='.')for(int k=0;k<4;k++){int x=i+g[k][0];int y=j+g[k][1];if(x<0||x>=n||y<0||y>=m||s[x][y]=='*')continue;B[id[i][j]][id[i][j]]++;B[id[i][j]][id[x][y]]=-1;}}}tol=tol-1;LL ans=determinant(tol); printf("%lld\n",ans);}
}