HEOI 2015 小 Z 的房间 题解
【HEOI 2015 小 Z 的房间 题解】题目传送门
题目大意： 求一张无向联通图的生成树个数。
题解
裸的M a t r i x ? T r e e Matrix-Tree Matrix?Tree 定理，就直接上代码了。
#include
#include
using namespace std;
#define mod 1000000000int n,m,t=0,id[10][10];
char s[10][10];
int f[110][110];
int fx[4]={-1,0,1,0};
int fy[4]={0,-1,0,1};
int det(int l)
{
int ans=1,fu=1;
for(int i=1;
i<=l;
i++)
{
for(int j=i+1;
j<=l;
j++)
while(f[j][i])
{
int p=f[i][i]/f[j][i];
for(int k=i;
k<=l;
k++)
f[i][k]=(1ll*f[i][k]-1ll*p*f[j][k]%mod+mod)%mod;
swap(f[i],f[j]);
fu=-fu;
}
if(!f[i][i])return 0;
ans=1ll*ans*f[i][i]%mod;
}
ans=(1ll*ans*fu+mod)%mod;
return ans;
}int main()
{
scanf("%d %d",&n,&m);
for(int i=1;
i<=n;
i++)scanf("%s",s[i]+1);
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=m;
j++)
if(s[i][j]=='.')id[i][j]=++t;
for(int i=1;
i<=n;
i++)for(int j=1;
j<=m;
j++)
if(s[i][j]=='.')for(int k=0;
k<4;
k++)
{
int x=i+fx[k],y=j+fy[k];
if(x<1||x>n||y<1||y>m||s[x][y]=='*')continue;
f[id[i][j]][id[i][j]]++;
f[id[i][j]][id[x][y]]=mod-1;
}
printf("%d",det(t-1));
}
推荐阅读
- 一个小故事，我的思考。
- 家乡的那条小河
- 一个人的碎碎念
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- 昨夜小楼听风
- 2021-02-17|2021-02-17 小儿按摩膻中穴-舒缓咳嗽
- 基于微信小程序带后端ssm接口小区物业管理平台设计
- 2019.4.18感恩日记
- 那件我们忽略的小事叫感恩
- 你有婚内虐待行为吗（）