UVA 10766 无向图的生成树计数

Matrix-Tree(矩阵树)定理

  • 需要线代的知识

    该定理解决了图的生成树计数问题

  1. N阶基尔霍夫(Kirchhhoff)矩阵的N-1阶子矩阵的行列式值就是无向图的生成树的个数

    kirchhhoff矩阵求法

    $K=D(度数矩阵)-A(邻接矩阵)$

度数矩阵特点

  • 度数:关联一个点的边的条数
    $D[i][j] != 0$ i=j
    $D[i][j] = 0$ i!=j
    除对角线外其余点都为0

    邻接矩阵

  • 用来存图中点和边的关系
  • 对角线上元素都为0
  • 这2个矩阵很好得到,会线代的现在就差如何用代码来行变换消元得到上三角矩阵(求行列式值)
  • 求$det(D_{n-1})$代码过程详细注释,高斯消元模板

UVA 10766 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 55;
#define ll long long int
ll a[maxn][maxn],b[maxn][maxn];
// 学过线代都知道求行列式的方法之一就是化成上\下三脚矩阵,对角线元素乘积是行列式值
ll determina(int n) {
	ll res = 1;
	for (int i = 1; i <= n; i++) {
		if (!b[i][i]) { //若果对角线元素为0,把此行都一都移到下一行去
			bool flag = false;
			for (int j = i + 1; j <= n; j++) { //从i+1行开始找i列中的第一个不为0的元素，与现在的行交换
				if (b[j][i]){//找到了该列不为0的元素,
					flag = 1; //标记,交换
					for (int k = i; k < n; k++) swap(b[i][k],b[j][k]);
					res = -res;// 换行系数变为负数
					break; //退出.
				}
			}
			if (!flag) return 0; //这一行全部为0,行列式值为0
		}

		for (int j = i + 1; j <= n;j++) {
			while (b[j][i]) { //从下面的行找一个不为0的元素与第i行进行消元
				ll t = b[i][i] / b[j][i]; 
				for (int k = i; k <= n; k++) {
					b[i][k] -= t * b[j][k];
					swap(b[i][k],b[j][k]);//消元后,把0的行换到下面来。
				}
				res = -res;
			}
		}
		res *= b[i][i];//对角线元素相乘
	}
	return res;
}
int main() {
//	freopen("a.txt","r",stdin);
	int n, m, k;
	while (scanf("%d%d%d",&n,&m,&k) != EOF) {
		memset(a, 0, sizeof a); memset(b,0,sizeof b);
		for (int i = 1; i <= m; i++) {
			int u, v; scanf("%d%d",&u,&v);
			a[u][v] = a[v][u] = 1; //把之间没有边的点都标记起来,
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i != j && !a[i][j]) { //扫描邻接矩阵
					b[i][i]++; //统计每个点的度数,右边则度数+1
					b[i][j] = -1;//减去邻接矩阵 把b直接更新为基尔霍夫矩阵
				}
			}
		}
		n -= 1; //求N-1阶矩阵的行列式,就是无向图的生成树的个数
		ll ans = determina(n);
		printf("%ld\n",ans);
	}
	return 0;
}