MatrixTree速成

前言

MatrixTree定理是用来解决生成树计数问题的有利工具

比如说这道题

MatrixTree定理的算法流程也非常简单

我们记矩阵A为无向图的度数矩阵 记矩阵D为无向图的邻接矩阵

A矩阵是除了对角线之外各个点值都为0的矩阵,A[i][i]表示i号点的度数

D矩阵记录两点之间的度数,D[i][j]表示i号点与j号点之间的边数

MatrixTree定理

我们记矩阵G=A-D 那么G的所有不同生成树的个数等于G的任何一个 n-1阶主子式的行列式的绝对值

实现

MatrixTree定理的实现非常简单

  1. 计算出D矩阵
  2. 后对其进行高斯消元
  3. 把消元后的矩阵的对角线乘起来
  4. 输出

代码

就是上面那道题目的代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=3001;
const double eps=1e-12;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
double G[MAXN][MAXN],a[MAXN][MAXN];
char s[MAXN][MAXN];
int xx[5]={0,-1,+1,0,0};
int yy[5]={0,0,0,-1,+1};
int N,M;
int dcmp(int x)
{
    if(x<=eps||x>=-eps) return 0;
    else return x<0?-1:1;
}
void Gauss()
{
    N--;
    for(int i=1;i<=N;i++)//每一行 
    {
        int mx=i;
        for(int j=i+1;j<=N;j++)//下面的每一行 
            if(dcmp(G[mx][i]-G[j][i])<0) mx=j;
        if(mx!=i) swap(G[i],G[mx]);
        if(!G[i][i]) {printf("0\n");return ;}
        for(int j=i+1;j<=N;j++)
        {
            double t=G[j][i]/G[i][i];
            for(int k=i;k<=N+1;k++)
                G[j][k]-=t*G[i][k];
        }
    }
    double ans=1;
    for(int i=1;i<=N;i++) ans=ans*G[i][i];
    printf("%.0f\n",abs(ans));
}
int main()
{  
    int T=read();
    while(T--)
    {
        memset(G,0,sizeof(G));
        N=read(),M=read();
        for(int i=1;i<=M;i++)
        {
            int x=read(),y=read();
            G[x][x]++;G[y][y]++;
            G[x][y]--;G[y][x]--;
        }
        Gauss();  
    }
    return 0;  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏转载gongluck的CSDN博客

H.264格式分析

一.H.264基本流结构 H.264 的基本流(elementary stream,ES)的结构分为两层,包括视频编码层(VCL)和网络适配层(NAL)。视频编...

81750
来自专栏技术专栏

Python3入门机器学习(三)- matplotlib基础与简单应用

33520
来自专栏冰霜之地

Google S2 中的 CellID 是如何生成的 ?

笔者在《高效的多维空间点索引算法 — Geohash 和 Google S2》文章中详细的分析了 Google S2 的算法实现思想。文章发出来以后,一部分读者...

41220
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

教程 OpenGL ES入门教程1-Tutorial01-GLKit OpenGL ES入门教程2-Tutorial02-shader入门 OpenGL E...

35350
来自专栏Phoenix的Android之旅

一张图看懂开发和运营的思维差别

用Dijkstra算法很简单,我们需要 · 用 6*6矩阵 source[6][6]表示点之间的距离,也就是图中的权值 · 自己与自己的距离为0,无直接连接的距...

8510
来自专栏数据结构与算法

BZOJ4517: [Sdoi2016]排列计数(组合数+错位排列)

Description 求有多少种长度为 n 的序列 A,满足以下条件: 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 的值为 i,则称 ...

30370
来自专栏ml

nyoj-----幸运三角形

幸运三角形 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述         话说有这么一个图形,只有两种符号组成(‘+’或者‘-’...

308100
来自专栏Flutter入门

Android OpenGL ES(二)-正交投影

平移矩阵和单位矩阵和类似。但是向量[x,y,z,1]前乘这个平移矩阵后的结构就是平移矩阵中定义的偏移量。

39510
来自专栏ml

编程之美 --1 : 骨牌覆盖问题·一

题目1 : 骨牌覆盖问题·一 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 骨牌,一种古老的玩具。今天我们要研究的是骨牌的覆盖问...

36650
来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

39990

扫码关注云+社区

领取腾讯云代金券