M_sea

「总结」矩阵树定理
内容首先定义邻接矩阵$\mathrm{G}$和入度矩阵$\mathrm{D}$,意思如名字。然后定义基尔霍夫矩阵$...
扫描右侧二维码阅读全文
28
2019/01

「总结」矩阵树定理

内容

首先定义邻接矩阵$\mathrm{G}$和入度矩阵$\mathrm{D}$,意思如名字。

然后定义基尔霍夫矩阵$\mathrm{C}=\mathrm{D}-\mathrm{G}$。

将基尔霍夫矩阵去掉对角线上的某一个位置所在行和所在列,形成了一个行列式。

或者说主对角线任意一个代数余子式。

然后计算这个行列式,结果就是生成树的个数。

事实上矩阵树定理求出的是 $\sum\limits_{T}\prod\limits_{e\in T}w_e$ 。

行列式

这东西还是我们澄池杯决赛讲的

性质

以下性质全都可以通过暴力拆式子证明。

  • 一个上三角矩阵的行列式是其对角线之积。
  • 交换两行/两列,行列式的值反号。
  • 行列式一行/一列乘以$k$,整个行列式的值乘以$k$。
  • 行列式两行/两列相加减,行列式的值不变。

求解

我们发现构造用的三种操作,正好是高斯消元的三种操作。

于是可以对这个行列式跑一遍高斯消元,得到一个上三角矩阵。

然后把每一步倒过来就可以求出行列式的值了。代码中只需要交换就反号,乘变除,除变乘就行啦。

这样就可以$O(n^3)$求解行列式的值了。

代码

$\text{a}$是上文中的$\text{C}$。

inline int calc() {
    int ans=1;
    for (re int i=2;i<=n;++i) {
        for (re int j=i+1;j<=n;++j)
            while (a[j][i]) {
                int t=a[i][i]/a[j][i];
                for (re int k=i;k<=n;++k) {
                    a[i][k]=(a[i][k]-a[j][k]*t%MOD+MOD)%MOD;
                    swap(a[i][k],a[j][k]);
                }
                ans=MOD-ans;
            }
        ans=ans*a[i][i]%MOD;
    }
    return (ans+MOD)%MOD;
}

例题

[CQOI2018]社交网络

有向图矩阵树定理的模板。

因为这题强制以$1$为根,所以只能删掉第一行和第一列。

[SDOI2014]重建

矩阵树定理的神仙应用。

习题

  • [SHOI2016]黑暗前的幻想乡

容斥+矩阵树定理。

最后修改:2019 年 05 月 13 日 08 : 29 PM

2 条评论

  1. smy

    有向图的和无向图的有区别,建议加上

    1. M_sea
      @smy

      晚点补qwq

发表评论