Matrix-Tree 矩阵树定理与生成树计数

Problem

n个点m条边的无向图,统计生成树个数。

Solution

前置技能

  • 矩阵的含义,基本运算
  • 行列式的含义,拉普拉斯展开

如何计算行列式

  • 以拉普拉斯展开式进行暴力递归计算
  • 将行列式转化为等价上三角行列式,计算$\prod ^n _{i=1} a_{ii}$

Matrix-Tree 定理

适用于不含重边的情况。 构造矩阵$\mathbf{D}$, 则 $$d_{ij}=\left\{\begin{matrix} d_i\ (i=j)\\ -1 \ (i\neq j,\ (i,j)\in E)\\ 0 \end{matrix}\right.$$

$d_i$为点i的度数。 矩阵$\mathbf{D}$的任意余子式的绝对值为该图的生成树个数。 一般选择$d_{nn}$的余子式计算。

n阶矩阵的余子式就是n阶矩阵的n-1阶主子式的行列式。

建议在了解前置技能的情况下观看文章(里面详细阐述了矩阵树定理的使用和行列式的求法):http://www.cnblogs.com/finder-iot/p/8662187.html 。建议前置技能通过结合维基百科和教材了解。

上面文章的求行列式的代码个人认为是个很好的模板。只是理解起来可能不是特别轻松,但其实还是好懂的。

例题-BZOJ4301 小Z的房间

模板题。
WA了一发,多加几个取模之后就好了。

// Code by ajcxsu
// Problem: room

#include<bits/stdc++.h>
#define MOD (1000000000ll)
using namespace std;
typedef long long ll;

const int N=100;
ll D[N][N]; // 矩阵
bool mp[N][N];
int idx[N][N], id;

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    char ch;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) {
            cin>>ch;
            if(ch=='.') mp[i][j]=1, idx[i][j]=id++;
        }
    int mv[]={0,1,0,-1,0};
    for(int i=0,ii,jj,u,v;i<n;i++)
        for(int j=0;j<m;j++) {
            if(!mp[i][j]) continue;
            for(int k=1;k<=4;k++) {
                ii=i+mv[k-1], jj=j+mv[k];
                if(ii>=0 && ii<n && jj>=0 && jj<m && mp[ii][jj]) {
                    u=idx[i][j], v=idx[ii][jj];
                    D[u][u]++;
                    D[u][v]=-1;
                }
            }
        }
    ll ans=1;
    for(int i=0;i<id-1;i++) for(int j=0;j<id-1;j++) D[i][j]%=MOD;
    for(int i=0;i<id-1;i++) {
        for(int j=i+1;j<id-1;j++) {
            while(D[j][i]) {
                ll tmp=D[i][i]/D[j][i];
                for(int k=0;k<id-1;k++) D[i][k]=((D[i][k]-D[j][k]*tmp)%MOD +MOD) % MOD;
                swap(D[i],D[j]), ans=-ans;
            } // 这个while很有灵性,因为是整数除,这样保证至少一行的i列元会被消为0.
        }
        ans=((ans*D[i][i])%MOD +MOD) % MOD;
        if(ans==0) break;
    }
    cout<<ans<<endl;
    return 0;
}

本文链接:https://acxblog.site/archives/matrix-tree.html
本文采用 CC BY-NC-SA 3.0 协议进行许可

    ju-ruo
    ju-ruo  2018-04-06, 19:11

    前来膜拜千古神犇yzk

    cx大水货
    cx大水货  2018-04-06, 19:34

    前来膜拜千古神犇,然而垃圾cx并没有资格%