BZOJ 4031 HEOI2015 小Z的房间 Matrix-Tree定理

题目大意:给定1张地图,求生成树个数
Matrix-Tree定理直接上
不过模数是109,不能直接求逆元
因此消元的时候展转相除1下就行了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 110
#define MOD 1000000000
using namespace std;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int m,n,tot;
char map[15][15];
int num[15][15];
long long f[M][M];
long long Gauss_Elimination(int n)
{
int i,j,k,mark=0;
for(i=1;i<=n;i++)
{
for(k=i;k<=n;k++)
if(f[k][i])
break;
if(k==n+1)
continue;
if(i!=k)
{
mark^=1;
for(j=i;j<=n;j++)
swap(f[i][j],f[k][j]);
}
for(k=i+1;k<=n;k++)
{
while(f[k][i])
{
int temp=f[k][i]/f[i][i];
for(j=i;j<=n;j++)
(f[k][j]+=MOD-f[i][j]*temp%MOD)%=MOD;
if(!f[k][i])
break;
mark^=1;
for(j=i;j<=n;j++)
swap(f[i][j],f[k][j]);
}
}
}
long long re=1;
for(i=1;i<=n;i++)
(re*=f[i][i])%=MOD;
if(mark)
re=(MOD-re)%MOD;
return re;
}
int main()
{
//freopen("room.in","r",stdin);
//freopen("room.out","w",stdout);
int i,j,k;
cin>>m>>n;
for(i=1;i<=m;i++)
{
scanf("%s",map[i]+1);
for(j=1;j<=n;j++)
if(map[i][j]=='.')
num[i][j]=++tot;
}
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(num[i][j])
for(k=0;k<4;k++)
{
int xx=i+dx[k];
int yy=j+dy[k];
if(!num[xx][yy])
continue;
f[num[i][j]][num[i][j]]++;
f[num[i][j]][num[xx][yy]]--;
}
for(i=1;i<=tot;i++)
for(j=1;j<=tot;j++)
if(f[i][j]<0)
f[i][j]+=MOD;
cout<<Gauss_Elimination(tot-1)<<endl;
return 0;
}
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » BZOJ 4031 HEOI2015 小Z的房间 Matrix-Tree定理

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡