矩阵树定理(Matrix Tree)学习笔记

如果不谈证明,稍微有点线代基础的人都可以在两分钟内学完所有相关内容。。

行列式随便找本线代书看一下基本性质就好了。

学习资源:

https://www.cnblogs.com/candy99/p/6420935.html

http://blog.csdn.net/Marco_L_T/article/details/72888138

首先是行列式对几个性质(基本上都是用数学归纳法证):

1.交换两行(列),行列式取相反数

2.由1.得若存在两行(列)完全相同则行列式为0

3.上(下)三角行列式即主对角线值之积

只有这三条用得上。

然后就可以直接上Matrix Tree定理了:一个无向图的邻接矩阵减去度数矩阵得到的矩阵的任意n-1阶子式的行列式的绝对值等于其有标号生成树的数目。

其中邻接矩阵-度数矩阵即为基尔霍夫矩阵(又称拉普拉斯算子)。

加强版:有向图的树形图(从根可以走到任意点)个数,将上面的“度数矩阵”改为“入度矩阵即可”(见第二份链接)

关于行列式的算法,按定义朴素跑复杂度是阶乘级别的,利用上面的性质,初等行变换使之成为上三角矩阵即可。(实际上就是高斯消元)。注意高消中基准元要选绝对值最大的,以及注意判0退出。

下面是几道裸题:

SPOJ Highways  裸题

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=l; i<=r; i++)
 6 using namespace std;
 7
 8 const int N=15;
 9 const double eps=1e-8;
10
11 int T,n,m,u,v;
12 double a[N][N];
13
14 void Gauss(){
15     n--;
16     rep(i,1,n){
17         int r=i;
18         rep(j,i+1,n) if (fabs(a[j][i])>fabs(a[r][i])) r=j;
19         if (fabs(a[r][i]<eps)) { puts("0"); return; }
20         if (r!=i) rep(k,1,n) swap(a[r][k],a[i][k]);
21         rep(j,i+1,n){
22             double t=a[j][i]/a[i][i];
23             rep(k,i,n) a[j][k]-=t*a[i][k];
24         }
25     }
26     double ans=1;
27     rep(i,1,n) ans*=a[i][i];
28     printf("%.0f\n",abs(ans));
29 }
30
31 int main(){
32     for (scanf("%d",&T); T--; ){
33         scanf("%d%d",&n,&m);
34         memset(a,0,sizeof(a));
35         rep(i,1,m) scanf("%d%d",&u,&v),a[u][u]++,a[v][v]++,a[u][v]--,a[v][u]--;
36         Gauss();
37     }
38     return 0;
39 }

BZOJ4766:

先手工构造出矩阵然后观察规律求出公式。

https://blog.sengxian.com/solutions/bzoj-4766

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5
 6 ll n,m,P;
 7 ll mod(ll x){ return (x<P) ? x : x-P; }
 8
 9 ll mul(ll a,ll b){
10     ll res=0;
11     for (; b; b>>=1,a=mod(a+a))
12         if (b & 1) res=mod(res+a);
13     return res;
14 }
15
16 ll pow(ll a,ll b){
17     ll res=1;
18     for (; b; b>>=1,a=mul(a,a))
19         if (b & 1) res=mul(res,a);
20     return res;
21 }
22
23 int main(){
24     scanf("%lld%lld%lld",&n,&m,&P);
25     printf("%lld\n",mul(pow(n,m-1),pow(m,n-1)));
26     return 0;
27 }

BZOJ4031 裸题

这里又个trick,高斯消元的时候因为模数是个合数不好求逆元,所以用辗转相除的方法做就好了。

就是不停对两行相互进行初等行变换直到其中一行第一个数变为0,这样复杂度是log的,并且保证膜意义下不会出错。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7
 8 const int N=105,md=1000000000;
 9 int n,m,a[N][N],id[N][N],tot;
10 char s[N][N];
11
12 void Gauss(int n){
13     int s=0;
14     rep(i,1,n){
15         int r=i;
16         rep(j,i+1,n) if (a[j][i]>a[r][i]) r=j;
17         if (!a[r][i]) { puts("0"); return; }
18         if (i!=r){
19             s^=1;
20             rep(k,i,n) swap(a[i][k],a[r][k]);
21         }
22         rep(j,i+1,n){
23             while (a[j][i]){
24                 ll t=a[j][i]/a[i][i];
25                 rep(k,i,n) a[j][k]=(a[j][k]-t*a[i][k]%md+md)%md;
26                 if (!a[j][i]) break;
27                 s^=1;
28                 rep(k,i,n) swap(a[i][k],a[j][k]);
29             }
30         }
31     }
32     ll ans=1;
33     rep(i,1,n) ans=ans*a[i][i]%md;
34     if (s) ans=(md-ans)%md;
35     printf("%lld\n",ans);
36 }
37
38 void work(){
39     rep(i,1,m) rep(j,1,n) if (s[i][j]==‘.‘) id[i][j]=++tot;
40     rep(i,1,m) rep(j,1,n) if (id[i][j]){
41         int u=id[i][j],v;
42         if (i!=1 && s[i-1][j]==‘.‘)
43             v=id[i-1][j],a[u][u]++,a[v][v]++,a[u][v]--,a[v][u]--;
44         if (j!=1 && s[i][j-1]==‘.‘)
45             v=id[i][j-1],a[u][u]++,a[v][v]++,a[u][v]--,a[v][u]--;
46     }
47     rep(i,1,m*n) rep(j,1,m*n) a[i][j]=(a[i][j]+md)%md;
48 }
49
50 int main(){
51     freopen("bzoj4031.in","r",stdin);
52     freopen("bzoj4031.out","w",stdout);
53     scanf("%d%d",&m,&n);
54     rep(i,1,m) scanf("%s",s[i]+1);
55     work(); Gauss(tot-1);
56     return 0;
57 }

原文地址:https://www.cnblogs.com/HocRiser/p/8481592.html

时间: 02-25

矩阵树定理(Matrix Tree)学习笔记的相关文章

@算法 - [email&#160;protected] matrix - tree 定理(矩阵树定理)

目录 @0 - 参考资料@ @0.5 - 你所需要了解的线性代数知识@ @1 - 定理主体@ @证明 part - [email protected] @证明 part - [email protected] @证明 part - [email protected] @证明 part - 4@ @2 - 一些简单的推广@ @3 - 例题与应用@ @0 - 参考资料@ MoebiusMeow 的讲解(超喜欢这个博主的!) 网上找的另外一篇讲解 @0.5 - 你所需要了解的线性代数知识@ 什么是矩阵

【算法】Matrix - Tree 矩阵树定理 &amp; 题目总结

最近集中学习了一下矩阵树定理,自己其实还是没有太明白原理(证明)类的东西,但想在这里总结一下应用中的一些细节,矩阵树定理的一些引申等等. 首先,矩阵树定理用于求解一个图上的生成树个数.实现方式是:\(A\)为邻接矩阵,\(D\)为度数矩阵,则基尔霍夫(Kirchhoff)矩阵即为:\(K = D - A\).具体实现中,记 \(a\) 为Kirchhoff矩阵,则若存在 \(E(u, v)\) ,则\(a[u][u] ++, a[v][v] ++, a[u][v] --, a[v][u] --\

【bzoj4894】天赋 矩阵树定理

题目描述 小明有许多潜在的天赋,他希望学习这些天赋来变得更强.正如许多游戏中一样,小明也有n种潜在的天赋,但有一些天赋必须是要有前置天赋才能够学习得到的.也就是说,有一些天赋必须是要在学习了另一个天赋的条件下才能学习的.比如,要想学会"开炮",必须先学会"开枪".一项天赋可能有多个前置天赋,但只需习得其中一个就可以学习这一项天赋.上帝不想为难小明,于是小明天生就已经习得了1号天赋-----"打架".于是小明想知道学习完这n种天赋的方案数,答案对1

spoj104 HIGH - Highways 矩阵树定理

欲学矩阵树定理必先自宫学习一些行列式的姿势 然后做一道例题 #include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; int T, n, m, uu, vv; double w[15][15]; const double eps=1e-7; void gauss(){ n--; for

luoguP3317 [SDOI2014]重建 变元矩阵树定理 + 概率

首先,我们需要求的是 $$\sum\limits_{Tree} \prod\limits_{E \in Tree} E(u, v) \prod\limits_{E \notin Tree} (1 - E(u, v))$$ 我们知道变元矩阵树定理 ---> 不知道请见此 我们自然希望要求和的事物只跟生成树的边有关 因此考虑把$\prod\limits_{E \notin Tree} (1 - E(u, v))$转化为$\prod\limits_{E} (1 - E(u, v)) * \frac{1

矩阵树定理速证

凯莱公式: spanning_trees_num( G ) = spanning_trees_num( G - e ) + spanning_trees_num( G · e ) 矩阵树定理: G 相应的拉普拉斯矩阵(度矩阵 - 邻接矩阵)L( G )   删除随意一行一列得到的行列式的值det( L*( G ) ) 即生成树的个数,即spanning_trees_num( G ) = det( L*( G ) ) 证: 归纳如果 spanning_trees_num( G - e ) = de

[spoj104][Highways] (生成树计数+矩阵树定理+高斯消元)

In some countries building highways takes a lot of time... Maybe that's because there are many possiblities to construct a network of highways and engineers can't make up their minds which one to choose. Suppose we have a list of cities that can be c

CSU 1805 Three Capitals(矩阵树定理+Best定理)

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1805 题意: A和B之间有a条边,A和G之间有b条边,B和G之间有c条边.现在从A点出发走遍所有的边,然后再回到A点,问一共有多少种方法. 思路: 16年湖南省赛题目,这道题目是求欧拉回路的个数,和生成树的计数有一定的联系. 首先给出神奇的Best定理,这是什么鬼定理,反正查不到什么有关该定理的文章... $ec(G)=t_s(G)\cdot deg(s)! \cdot \prod_{v\i

【BZOJ4031】[HEOI2015]小Z的房间 矩阵树定理

[BZOJ4031][HEOI2015]小Z的房间 Description 你突然有了一个大房子,房子里面有一些房间.事实上,你的房子可以看做是一个包含n*m个格子的格状矩形,每个格子是一个房间或者是一个柱子.在一开始的时候,相邻的格子之间都有墙隔着. 你想要打通一些相邻房间的墙,使得所有房间能够互相到达.在此过程中,你不能把房子给打穿,或者打通柱子(以及柱子旁边的墙).同时,你不希望在房子中有小偷的时候会很难抓,所以你希望任意两个房间之间都只有一条通路.现在,你希望统计一共有多少种可行的方案.