ZigZagK的博客
[矩阵树定理]SPOJ(HIGH)【Highways】题解
2019年1月8日 09:34
图论,SPOJ
查看标签

题目概述

给出一张无向图,求生成树个数。

解题报告

大佬传送门:*ZJCandy?

矩阵树定理裸题,先来讲(瞎扯)一波行列式:

行列式定义式:$Det(A)=\sum_{P}(-1)^{\tau(P)}\sum_{i=1}^{n}A_{i,P_i}$ ,其中 $A$ 是 $n$ 行 $n$ 列矩阵,$P$ 是 $n$ 的排列,$\tau(P)$ 是 $P$ 的逆序对数。

$n-1$ 阶主子式:删除 $i$ 行 $i$ 列后得到的新矩阵。

行列式性质们:

  1. $Det(A)=Det(A^{T})$

    • 定义式展开都是对应的,Candy?表示这说明了行列平等。
  2. 两行或两列互换,行列式变号

    • 考虑一个序列两个元素交换后逆序对变化是奇数(我好像在之间就见过这个性质,但我不记得了QAQ),所以行列式就变号了。由此得知矩阵如果两行或两列相同,那么行列式为 $0$ 。
  3. 单行单列乘上一个数 $k$ ,行列式 $\times k$

    • 考虑定义式,可以把 $k$ 提取出来。由此得知矩阵如果两行成比例,行列式也为 $0$ 。
  4. 如果 $A,B$ 只有一行或一列不同,那么 $Det(A)+Det(B)$ 等于那一行或一列加起来后的矩阵的行列式

    • 考虑定义式,新矩阵的行列式显然可以拆成 $Det(A)+Det(B)$ 。
  5. 很重要的性质:把矩阵的一行(列)乘上 $k$ 加到另外一行(列)上,行列式不变

    • 根据性质 $3$ 和 $4$ ,新矩阵的行列式可以拆成两个,其中一个是原矩阵的行列式,另一个是加到的行(列)变成 $k$ 倍的被加的行(列)的矩阵的行列式,第二个矩阵两行(列)成比例,行列式为 $0$ 。

根据上述性质(尤其是性质 $5$ )我们可以用高斯消元来得出行列式。


基尔霍夫矩阵:一张图的度数矩阵减去邻接矩阵。度数矩阵:$A_{i,i}$ 为 $i$ 点度数,其余为 $0$ 。邻接矩阵:$A_{i,j}$ 表示 $i,j​$ 之间边的个数。

矩阵树定理:一张图的生成树个数是该图基尔霍夫矩阵的任意一个 $n-1$ 阶主子式的行列式。

证明我试图去看了……但是,毕竟是试图QAQ……

示例程序

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long double DB;
const int maxn=12;

int te,n,m;DB a[maxn+5][maxn+5],ans;

inline int fcmp(DB a,DB b) {if (fabs(a-b)<1e-8) return 0;return a<b?-1:1;}
inline double Det(int n,DB ans=1){
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++) if (fcmp(a[j][i],0)>0) {if (i!=j) swap(a[i],a[j]),ans=-ans;goto YES;}
        return 0;YES:for (int j=i+1;j<=n;j++) {DB t=a[j][i]/a[i][i];for (int k=i;k<=n;k++) a[j][k]-=t*a[i][k];}
    }for (int i=1;i<=n;i++) ans*=a[i][i];return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);memset(a,0,sizeof(a));
        for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),a[x][x]++,a[y][y]++,a[x][y]--,a[y][x]--;
        printf("%.0f\n",fabs(Det(n-1)));
    }return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!