生成树计数 Matrix-Tree 定理

一直都知道要用Matrix-Tree定理来解决生成树计数问题,但是拖到今天才来学。博主数学不好也只能跟着各位大佬博客学一下它的应用以及会做题,证明实在是不会。

推荐博客https://blog.csdn.net/u011815404/article/details/89091011(Matrix-Tree定理)

https://blog.csdn.net/u011815404/article/details/99679527(写得无敌好的生成树计数了)

那么比较常见的生成树计数问题就三种:①生成树计数②同边权边较少的MST计数③同边权边较少的MST计数,针对这3个问题有3种解决办法。

最简单的生成树计数就是Matrix-Tree定理的模板题啦,直接求出Kirchhoff 矩阵然后求它的n-1阶行列式绝对值。

Highways

代码抄袭参考的大佬的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10+5;
int n,m;

LL K[N][N];
LL det(int n){  //求矩阵K的n-1阶顺序主子式
    LL ret=1;
    for(int i=1;i<=n-1;i++){  //枚举主对角线上第i个元素
        for(int j=i+1;j<=n-1;j++){  //枚举剩下的行
            while(K[j][i]){  //辗转相除
                int t=K[i][i]/K[j][i];
                for(int k=i;k<=n-1;k++)  //转为倒三角
                    K[i][k]=K[i][k]-t*K[j][k];
                swap(K[i],K[j]);  //交换i、j两行
                ret=-ret;  //取负
            }
        }
        ret=ret*K[i][i];
    }
    return abs(ret);
}

int main()
{
    int T; cin>>T;
    while (T--) {
        scanf("%d%d",&n,&m);
        memset(K,0,sizeof(K));
        for (int i=1;i<=m;i++) {
            int x,y; scanf("%d%d",&x,&y);
            K[x][x]++; K[y][y]++;
            K[x][y]--; K[y][x]--;
        }
        printf("%lld\n",det(n));
    }
    return 0;
} 

MST计数的话,如果同边权边较少的话可以考虑用暴力。它基于MST的两条性质:

  • 每种权值的边的数量是固定的
  • 不同的生成树中,某一种权值的边任意加入需要的数量后,形成的联通块状态是相同的

意思就是对于所有的MST对于边权例如为w的边的数量是一定的。这就启发我们暴力搜索每种边权选的使用的边,然后用乘法原理计算出方案数。这种办法因为是枚举所有的使用同边权使用情况所以时间复杂度是O(2^k*m)(k是同边权边数)。但是因为这个解法有局限性所以也不是特别有用。

去掉同边权边数限制的话就是更广泛的最小生成树计数了,要用到缩点+Matrix-Tree定理的解法。具体就是还是枚举每个边权i,然后把非边权i的边加入到图中然后缩点,对缩完点之后的图求Kirchhoff 矩阵利用Matrix-Tree定理求出生成树个数那么这个就是边权i的方案数了,然后全部边权乘法原理乘起来就是答案了。

洛谷P4208 最小生成树计数

给出一幅图求MST数量,缩点+Matrix-Tree定理解决。(这道题的数据也可以用暴力搜索解决)

代码还没写这里先贴个大佬的模板:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
const int MOD = 31011;
const int N = 1000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;

struct Edge {
    int x,y;
    int dis;
    bool operator < (const Edge &rhs) const {
        return dis<rhs.dis;
    }
} edge[N],tr[N];
int n,m;
int father[N];
int G[N][N];
int tot,bel[N],val[N];
int Find(int x) {
    if(father[x]!=x)
        return father[x]=Find(father[x]);
    return x;
}
int Gauss(int n) {
    int res=1;
    for(int i=1; i<=n; i++) {
        for(int k=i+1; k<=n; k++) {
            while(G[k][i]) {
                int d=G[i][i]/G[k][i];
                for(int j=i; j<=n; j++)
                    G[i][j]=(G[i][j]-1LL*d*G[k][j]%MOD+MOD)%MOD;
                swap(G[i],G[k]);
                res=-res;
            }
        }
        res=1LL*res*G[i][i]%MOD,res=(res+MOD)%MOD;
    }
    return res;
}
int Kruskal() {
    sort(edge+1,edge+m+1);
    for(int i=1; i<=n; i++)
        father[i]=i;
    int cnt=0;
    for(int i=1; i<=m; i++) {
        int fu=Find(edge[i].x);
        int fv=Find(edge[i].y);
        if(fu==fv)
            continue;
        father[fu]=fv,tr[++cnt]=edge[i];
        if(edge[i].dis!=val[tot])
            val[++tot]=edge[i].dis;
    }
    return cnt;
}
void addTreeEdge(int v) {
    for(int i=1; i<n&&tr[i].dis!=v; i++){
        int x=tr[i].x;
        int y=tr[i].y;
        father[Find(x)]=Find(y);
    }
    for(int i=n-1; i&&tr[i].dis!=v; i--){
        int x=tr[i].x;
        int y=tr[i].y;
        father[Find(x)]=Find(y);
    }
}
void rebuild(int v) {
    memset(G,0,sizeof(G));
    for(int i=1; i<=m; i++){
        if(edge[i].dis==v){
            int x=bel[edge[i].x];
            int y=bel[edge[i].y];
            G[x][y]--;
            G[y][x]--;
            G[x][x]++;
            G[y][y]++;
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].dis);

    int cnt=Kruskal();
    if(cnt!=n-1) {
        printf("0\n");
    }
    else{
        int res=1;
        for(int i=1; i<=tot; i++) {
            for(int i=1; i<=n; i++)
                father[i]=i;

            addTreeEdge(val[i]);

            int blo=0;
            for(int i=1; i<=n; i++)
                if(Find(i)==i)
                    bel[i]=++blo;
            for(int i=1; i<=n; i++)
                bel[i]=bel[Find(i)];

            rebuild(val[i]);
            res=1LL*res*Gauss(blo-1)%MOD;
        }
        printf("%d\n",res);
    }
    return 0;
}

原文地址:https://www.cnblogs.com/clno1/p/11420707.html

时间: 08-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 - 你所需要了解的线性代数知识@ 什么是矩阵

HDU 4305 Lightning Matrix Tree定理

题目链接:https://vjudge.net/problem/HDU-4305 解法:首先是根据两点的距离不大于R,而且中间没有点建立一个图.之后就是求生成树计数了. Matrix-Tree定理(Kirchhoff矩阵-树定理).Matrix-Tree定理是解决生成树计数问题最有力的武器之一.它首先于1847年被Kirchhoff证明.在介绍定理之前,我们首先明确几个概念: 1.G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时,dij=0:当i=j时,dij等于vi的度数. 2.G

[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

【生成树计数】Matrix-tree定理学习笔记

学完了矩阵和行列式基础知识,终于可以去学矩阵数定理~(≧▽≦)/~ -----------–线割分是我>w<---------------– Matrix-tree定理,又叫Kirchhoff矩阵定理,于1847年首次被基尔霍夫先生证明,后来被广泛应用于生成树的计数问题. 要用它,需要先知道几个重要概念: 无向图的度数矩阵和邻接矩阵. 假定有无向图G,图中共有n个点. G的度数矩阵称D[G],邻接矩阵称A[G].这两个矩阵的大小都是n*n的. 对于D[G],他满足: di,j={0,     

矩阵树定理(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.上(下)三角行列式即主

kuangbin带你飞 生成树专题 : 次小生成树; 最小树形图;生成树计数

第一个部分 前4题 次小生成树 算法:首先如果生成了最小生成树,那么这些树上的所有的边都进行标记.标记为树边. 接下来进行枚举,枚举任意一条不在MST上的边,如果加入这条边,那么肯定会在这棵树上形成一个环,如果还要维护处树的特点 那么就要在这个环上删去一条边,这样他还是树,删掉的边显然是这条链上权值最大边更可能形成次小生成树.那么就有2中方法可以做. 第一种PRIM在prim时候直接可以做出这个从I到J的链上权值最大的值MAX[i][j]; 同时可以用kruskal同样方式标记树边,然后DFS跑

【BZOJ1002】【FJOI2007】轮状病毒 生成树计数推导。 Python代码

突然学了一小下Python 算是勉强会写点了. 至于这道题的题解,就是根据Matrix Tree定理,然后Kirchhoff矩阵高斯消元就好了, 不过这道题如果消去中心点的行和列做的话,矩阵会很规矩,然后貌似"手算"可以推出公式(VFK Orz,手算--) VFK's blog:http://vfleaking.blog.163.com/blog/static/17480763420119685112649/ 然后下面是Python代码,算是裸语法吧. n=int(raw_input(

生成树计数

生成树计数就是统计一张图中一共有多少种构造生成树的方案. 大概要用到组合数学等等的数学知识. 以下内容均来自NOI2007国家集训队论文 周冬 <生成树的计数及其应用>: ------------------------- Matrix-Tree定理(Kirchhoff矩阵-树定理).Matrix-Tree定理是解决生成树计数问题最有力的武器之一.它首先于1847年被Kirchhoff证明.在介绍定理之前,我们首先明确几个概念: 1.G的度数矩阵D[G]是一个n*n的矩阵,并且满足:当i≠j时

Uva 10766 Organising the Organisation (Matrix_tree 生成树计数)

题目描述: 一个由n个部门组成的公司现在需要分层,但是由于员工间的一些小小矛盾,使得他们并不愿意做上下级,问在满足他们要求以后有多少种分层的方案数? 解题思路: 生成树计数模板题,建立Kirchhoff矩阵,利用Matrix_tree定理求解. Kirchhoff矩阵:假设G为n*n矩阵,C为G的入度矩阵(i==j时,C[i][j]等于i的入度;i!=j时,C[i][j]等于零),A为G的邻接矩阵,那么就有Kirchhoff矩阵等于C-A. Matrix_tree定理:G的不同生成树的个数等于其