【bzoj4031】[HEOI2015]小Z的房间

题解：

矩阵树定理入门题

一个图的邻接矩阵G：对于无向图的边(u,v)，G[u][v]++,G[v][u]++

一个图的度数矩阵D：对于无向图的边(u,v)，D[u][u]++,D[v][v]++;

而通过这两个矩阵就可以构造出图G的基尔霍夫矩阵：C=D-G.

Matrix Tree定理：将图G的基尔霍夫矩阵去掉第i行和第i列(i可以取任意值，可以证明所得到的结果相同)，得到(n-1)*(n-1)的矩阵

Part 2 Matrix Tree定理在有向图上的拓展

Matrix Tree定理的拓展与延伸------有向图的Matrix Tree定理

对于有向图G，不存在生成树的概念，但存在树形图的概念。

树形图：以i点为根节点的树形图有(n-1)条边，从i节点出发可以到达其他所有(n-1)个节点.

定义：有向图的邻接矩阵G：对于有向图的边(u,v)，G[u][v]++.

有向图的度数矩阵D：对于有向图的边(u,v)，D[v][v]++.

尤其需要注意的是：有向图的度数矩阵指的是一个点的入度，而不是出度。

而有向图的基尔霍夫矩阵的构造方式是一模一样的：C=D-G.

有向图Matrix Tree定理：

将有向图G的基尔霍夫矩阵去掉第i行和第i列，得到(n-1)*(n-1)的矩阵，

对这个矩阵进行行列式的值求解，abs(det(A))就是以i为根的树形图的个数。

行列式相关结论：

行列式与它的转置行列式相等；
互换行列式的两行（列），行列式变号；
行列式的某一行（列）的所有的元素都乘以同一数k，等于用数k乘此行列式；
行列式如果有两行（列）元素成比例，则此行列式等于零；
若行列式的某一列（行）的元素都是两数之和，则这个行列式是对应两个行列式的和；
把行列式的某一列（行）的各元素乘以同一数然后加到另一列（行）对应的元素上去，行列式不变

在求解行列式时，我们利用高斯消元将其变为上三角矩阵，答案就是pai(a[i][i])

另外注意到高斯消元中有除法运算，但是这题中的模数并没有逆元，所以我们用辗转相除来减

另外注意到交换两行符号变号要记录一下

另外不是房间的点不要算

代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define rint register ll

const ll mo=1e9;

char ss[<<],*A=ss,*B=ss;

char gc()

{

  return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

}

template<class T> void read(T &x)

{

  rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;

  while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^);

}

ll n,m,s;

ll a[][],ff[][];

ll guass()

{

  s--;

  int cnt=;

  for (ll i=;i<=s;i++)

  {

   /* ll now=i;

    for (ll j=i+1;j<=s;j++)

      if (abs(a[j][i])>abs(a[now][i])) now=j;

    if (now!=i)

      for (ll j=1;j<=s;j++) swap(a[i][j],a[now][j]); */

    for (ll j=i+;j<=s;j++)

      while (a[j][i])

      {

        ll kk=a[i][i]/a[j][i];

        for (ll k=;k<=s;k++) a[i][k]=(a[i][k]-kk*a[j][k])%mo;

        for (ll k=;k<=s;k++) swap(a[i][k],a[j][k]);

        cnt++;

      }

  }

  ll ans=; if (cnt%) ans=-;

  for (ll i=;i<=s;i++)

    ans=(ans*a[i][i])%mo;

  return (ans+mo)%mo;

}

ll js(ll x,ll y)

{

  return(ff[x][y]);

}

void cl(ll x1,ll y1,ll x2,ll y2)

{

  ll k1=js(x1,y1),k2=js(x2,y2);

  a[k1][k2]--; a[k2][k2]++;

}

char c[][];

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  ios::sync_with_stdio(false);

  cin>>n>>m;

  for (ll i=;i<=n;i++) cin>>c[i];

  int num=;

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

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

      if (c[i][j-]=='.') ff[i][j]=++num;

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

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

    {

      if (i!=n)

        if (c[i][j-]=='.'&&c[i+][j-]=='.')

          cl(i,j,i+,j);

      if (i!=)

        if (c[i][j-]=='.'&&c[i-][j-]=='.')

          cl(i,j,i-,j);

      if (j!=m)

        if (c[i][j-]=='.'&&c[i][j]=='.')

          cl(i,j,i,j+);

      if (j!=)

        if (c[i][j-]=='.'&&c[i][j-]=='.')

          cl(i,j,i,j-);

    }

  s=num;

  /*for (int i=1;i<=s-1;i++)

  {

    cout<<endl;

    for (int j=1;j<=s-1;j++)

      cout<<a[i][j]<<" ";

  }

  cout<<endl;*/

  cout<<guass();

  /* for (int i=1;i<=s;i++)

  {

    cout<<endl;

    for (int j=1;j<=s;j++)

      cout<<a[i][j]<<" ";

  }

  cout<<endl;*/

  return ;

}

秒客网

【bzoj4031】[HEOI2015]小Z的房间

相关文章