p4111 [HEOI2015]小Z的房间[简述矩阵树定理]

分析

[1]无向图

图G的度数矩阵为D,邻接矩阵为A

我们定义这个图的Kirchhoff矩阵为D-A

这个矩阵的任意一个n-1阶主子式的行列式的绝对值就是这个图的生成树个数

[2]有向图

如果要求内向树计数,矩阵是出度矩阵-邻接矩阵
如果要求外向树计数,矩阵是入度矩阵-邻接矩阵
注意有向树计数的时候,删除一行一列,必须删除根所在的行列。

对于这个题我们只需要将一个点与周围的非障碍点连边

然后求无向图的生成树个数即可

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const int mod = 1e9;

const int dx[] = {,,,-};

const int dy[] = {,-,,};

int n,m,g[][],wh[][],cnt;

char s[][];

inline int gs(){

    int i,j,k,ans=;

    for(i=;i<=n;i++)

      for(j=;j<=n;j++)

        g[i][j]=(g[i][j]%mod+mod)%mod;

    for(i=;i<=n;i++){

      for(j=i;j<=n;j++)

        if(g[i][j])break;

      if(j>n)return ;

      if(j!=i)ans=mod-ans,swap(g[i],g[j]);

      for(j=i+;j<=n;j++){

          while(g[j][i]){

            int t=g[i][i]/g[j][i];

            for(k=i;k<=n;k++)

              g[i][k]=(g[i][k]-1ll*t*g[j][k]%mod+mod)%mod;

            swap(g[i],g[j]);

            ans=mod-ans;

          }

      }

      ans=1ll*ans*g[i][i]%mod;

    }

    return ans;

}

int main(){

    int i,j,k;

    scanf("%d%d",&n,&m);

    for(i=;i<=n;i++){

      scanf("%s",s[i]+);

      for(j=;j<=m;j++)

        if(s[i][j]=='.')

          wh[i][j]=++cnt;

    }

    for(i=;i<=n;i++)

      for(j=;j<=m;j++){

          if(!wh[i][j])continue;

          for(k=;k<;k++)

            if(wh[i+dx[k]][j+dy[k]]){

                int id=wh[i][j];

                g[id][id]++;

                g[id][wh[i+dx[k]][j+dy[k]]]--;

            }

      }

    n=cnt-;

    printf("%d\n",gs());

    return ;

}

巴特西

p4111 [HEOI2015]小Z的房间[简述矩阵树定理]

最新文章

热门文章