矩阵树定理(+行列式) 更新于 2026/7/10 10:03:28 作者

command_block

本文同时也作为P6178的题解。

1.行列式基础

• 行列式的定义

对于一个矩阵 $A[1...n][1...n]$ ,其行列式为

$\det(A)=\sum\limits_{P}(-1)^{\mu(P)}\prod\limits_{i=1}^nA[i][p_i]$

(枚举排列 $P[1...n]$ ,其中 $\mu(P)$ 为排列 $P$ 的逆序对数)

( $\det(A)$ 又作 $|A|$ )

也就是说在每一行挑一个乘起来,然后再拿逆序对有关的东西做系数。

直接按照定义计算,复杂度是 $O(n!·n)$ 的。

• 行列式的性质

知道了下面几条性质之后,我们就能快速计算行列式了。

• (0) 单位矩阵 $I$ 的行列式为 $1$ 。

这个比较显然,因为 $P$ 除了对角线之外没有别的选择,而对角线乘积为 $1$。

类似的,上三角矩阵和下三角矩阵的行列式都是对角线乘积。

• (1) 交换矩阵的两行,行列式变号。

(根据逆序对感性理解即可)

我们考虑对于每个排列,这一次交换只会影响乘积组前面的逆序对系数。

对于任意一个序列,交换两个数对于逆序对个数的影响必定为奇数(可以自己讨论一下)。

所以逆序对系数全部都改变,即变号。

• (2) 若某一行乘以 $t$ ,行列式就也乘以 $t$ 。

这个比较好理解,因为这一行选且只选一个嘛。

• (3) 看公式:

$\begin{vmatrix}a+a'&b+b'\\c&d\end{vmatrix}=\begin{vmatrix}a&b\\c&d\end{vmatrix}+\begin{vmatrix}a'&b'\\c&d\end{vmatrix}$

还是因为一行选且只选一个,然后乘法分配律就好了。

(2,3合起来就是行的线性性)

• (4) 有某两行一样的矩阵,行列式是 $0$.

这个证明比较巧妙 : 考虑交换相同的这两行,根据(1)得行列式变号。

但是矩阵并没有实质的改变,行列式不变,所以行列式的值只能是 $0$.

• (5) 用矩阵的一行加上另一行的倍数,行列式不变。

考虑构造(省略的部分表示不变):

欲证$\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d+ka&e+kb&f+kc\end{vmatrix}$

首先构造一个$\begin{vmatrix}a&b&c\\.&.&.\\a&b&c\end{vmatrix}$,根据(4)得其值为0.

又根据(2)得$\begin{vmatrix}a&b&c\\.&.&.\\ka&kb&kc\end{vmatrix}$也为0。

然后根据(3)得

$$\begin{vmatrix}a&b&c\\.&.&.\\d+ka&e+kb&f+kc\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}+\begin{vmatrix}a&b&c\\.&.&.\\ka&kb&kc\end{vmatrix}=\begin{vmatrix}a&b&c\\.&.&.\\d&e&f\end{vmatrix}$$

• 消元求行列式

其实我们上面证明的性质,就是为这个来打基础的。

我们消元的时候,只是用了 {交换两行, 某一行乘一个常数, 一行加上另一行的倍数} 三种操作。

那么,我们对于 $A$ 进行消元,然后记录操作对于行列式的影响,最后得到上三角矩阵,行列式就是对角线乘积,如果消不出来那么返回 $0$。

最后再把影响逆回去即可。

2.矩阵树定理与部分扩展

(默认图中无自环)

• 经典

给出一个无向无权图,设 $A$ 为邻接矩阵, $D$ 为度数矩阵( $D[i][i]=$节点 $i$ 的度数,其他的无值)。

则基尔霍夫(Kirchhoff)矩阵即为 : $K=D-A$

然后令 $K'$ 为 $K$ 去掉第k行与第k列(k任意)的结果($n-1$阶主子式),

$\det(K')$ 即为该图的生成树个数。

证明不会。感兴趣的同学可以自行百度。

例题 : P4336 [SHOI2016]黑暗前的幻想乡

• 加权扩展

容易理解 : 带重边的情况,上面的经典矩阵树定理也是能够处理的。

根据乘法原理,对于某种生成树的形态,其贡献为每条边重的次数的乘积。

如果把重边次数理解成权值的话,那么矩阵树定理求的就是 : 所有生成树边权乘积的总和。

(这里注意度数矩阵变成了相邻边的权值和)

例题 : P3317 [SDOI2014]重建

• 有向扩展

前面都是无向图,神奇的是有向图的情况也是可以做的。

(邻接矩阵 $A$ 的意义同有向图邻接矩阵)

那么现在的矩阵 $D$ 就要变一下了。

若 $D[i][i]=\sum\limits_{j=1}^nA[j][i]$ ,即到该点的边权总和(入)。

此时求的就是外向树 (从根向外)

若 $D[i][i]=\sum\limits_{j=1}^nA[i][j]$ ,即从从该点出发的边权总和(出)。

此时求的就是内向树 (从外向根)

(如果考场上不小心忘掉了,可以手玩小样例)

(同样可以加权!)

此外,既然是有向的,那么就需要指定根。

前面提过要任意去掉第 $k$ 行与第 $k$ 列,是因为无向图所以不用在意谁为根。

在有向树的时候需要理解为指定根,结论是 : 去掉哪一行就是那一个元素为根。

例题 : P4455 [CQOI2018]社交网络 (内向树)

本题就是外向树,下面给出代码(出乎意料,跑的还挺快)。

#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 1000000007
#define Maxn 305
using namespace std;
ll powM(ll a,int t=mod-2)
{
  ll ans=1;
  while(t){
    if (t&1)ans=ans*a%mod;
    a=a*a%mod;t>>=1;
  }return ans;
}
int n,m;
ll *a[Maxn],_a[Maxn][Maxn];
ll det(ll **a)
{
  ll ans=1;bool tr=0;
  for (int j=1;j<n;j++){
    for (int i=j;i<n;i++)
      if (a[i][j]){
        if (i!=j){
          swap(a[i],a[j]);
          tr=!tr;
        }break;
      }
  	if (a[j][j]==0)return 0;
  	ans=ans*a[j][j]%mod;
  	ll t=powM(a[j][j]);
  	for (int k=j;k<n;k++)a[j][k]=t*a[j][k]%mod;
    for (int i=j+1;i<n;i++){
  	  t=mod-a[i][j];
  	  for (int k=j;k<n;k++)
  	    a[i][k]=(a[i][k]+t*a[j][k])%mod;
    }
  }return tr? (mod-ans)%mod : ans;
}
int op;
int main()
{
  scanf("%d%d%d",&n,&m,&op);
  for (int i=1;i<=n;i++)a[i]=_a[i];
  for (int i=1,f,t,w;i<=m;i++){
    scanf("%d%d%d",&f,&t,&w);
    if (f==n)f=1;else if (f==1)f=n;
    if (t==n)t=1;else if (t==1)t=n;
    if (op==1){
      a[f][t]=(a[f][t]-w+mod)%mod;
      a[t][t]=(a[t][t]+w)%mod;
    }else {
      a[f][t]=(a[f][t]-w+mod)%mod;
      a[t][t]=(a[t][t]+w)%mod;
      a[t][f]=(a[t][f]-w+mod)%mod;
      a[f][f]=(a[f][f]+w)%mod;
    }
  }printf("%lld",det(a));
  return 0;
}