首页 > 代码库 > BZOJ 4031 [HEOI2015]小Z的房间（Matrix-Tree定理）
BZOJ 4031 [HEOI2015]小Z的房间（Matrix-Tree定理）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4031
【题目大意】
你突然有了一个大房子，房子里面有一些房间。
事实上，你的房子可以看做是一个包含n*m个格子的格状矩形，
每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。
你想要打通一些相邻房间的墙，使得所有房间能够互相到达。
在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。
同时，你不希望在房子中有小偷的时候会很难抓，
所以你希望任意两个房间之间都只有一条通路。现在，你希望统计一共有多少种可行的方案。
【题解】
根据任意两个房间之间只有一条通路我们可以知道这题要求的是生成树的方案数，
那么我们先求出这个图的基尔霍夫矩阵，然后求余子式就是答案，处理一下取模即可。
【代码】
#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;#define rep(i,n,m) for(int i=n;i<=m;i++)const LL mod=1000000000;int dx[]={0,0,1,-1},dy[]={1,-1,0,0};int n,m,id;char mp[110][110];LL a[110][110],p[110][110];int det(int n){ LL ans=1,f=1; rep(i,1,n)rep(j,1,n)a[i][j]=(a[i][j]+mod)%mod; rep(i,1,n){ rep(j,i+1,n){ LL A=a[i][i],B=a[j][i]; while(B!=0){ LL t=A/B; A%=B; swap(A,B); for(int k=1;k<=n;k++)a[i][k]=(a[i][k]-t*a[j][k]%mod+mod)%mod; for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]); f=-f; } }if(!a[i][i])return 0; ans=ans*a[i][i]%mod; }if(f==-1)return (mod-ans)%mod; return ans;}bool check(int x,int y){if(x<1||y<1||x>n||y>m||mp[x][y]!=‘.‘)return 0;return 1;}int main(){ scanf("%d%d",&n,&m); rep(i,1,n)scanf("%s",mp[i]+1); rep(i,1,n)rep(j,1,m)if(mp[i][j]==‘.‘)p[i][j]=++id; rep(i,1,n)rep(j,1,m)if(mp[i][j]==‘.‘){ rep(k,0,4){ int x=i+dx[k],y=j+dy[k]; if(check(x,y)){int u=p[i][j],v=p[x][y];a[u][u]++;a[u][v]--;} } }printf("%d\n",det(id-1)); return 0;}BZOJ 4031 [HEOI2015]小Z的房间（Matrix-Tree定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。