加载中...

矩阵树定理

发表于2023-11-07|OI（高中）2023-2024赛季

|总字数:258|阅读时长:1分钟|浏览量:

矩阵树定理

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132152078

启蒙： http://zhengruioi.com/contest/1416 T1，T2的10分暴力（后面是论文科技，不搞了）

https://www.luogu.com.cn/problem/P6178

$O(n^3)$ 解决无向图生成树计数问题。

行列式

交换两行，行列式变号
一行整体加上 $k$ 倍另一行，行列式符号不变
行列式如果只有其中对角线非0，那么它的值就是对角线上值的乘积
矩阵树定理好像要求余子式，至于为啥oi不用管，记结论就行

构造

构造一个度数矩阵， $f[x][x]$ 表示 $x$ 的度数（外向树为出度，内向树为入度）， $g[x][y]$ 表示 $x\to y$ 这条边的边权。然后令 $h=f-g$ ，求 $h$ 的行列式即可。

建图

在这里插入图片描述

计算行列式

在这里插入图片描述

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/9102718b

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

图论算法矩阵

相关推荐

【CF1120D Power Tree】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15839195.html 题目链接题目 You are given a rooted tree with n n n vertices, the root of the tree is the vertex 1 1 1 . Each vertex has some non-negative price. A leaf of the tree is a non-root vertex that has degree 1 1 1 . Arkady ...

【P5994 [PA2014]Kuglarz】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15838986.html 题目链接题目魔术师的桌子上有 nnn 个杯子排成一行，编号为 1,2,…,n1,2,…,n1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费 cijc_{ij}cij 元，魔术师就会告诉你杯子 i,i+1,…,ji,i+1,…,ji,i+1,…,j 底下藏有球的总数的奇偶性。采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？思路前缀和建图...

欧拉回路/路径求法

欧拉回路/路径求法本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132082624 以任意一点/奇数度点开始dfs，能走就走，遍历所有边，离开时加入点。 1234567void dfs(int x) { for(; t[x]<G[x].size(); ) { int y=G[x][t[x]]; ++t[x]; dfs(y); } z.push(x); }

点分治小结

点分治小结本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...

无源汇上下界可行流

无源汇上下界可行流本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091530 新建两个超级源、汇点。原先是a->b，范围[c,d]。现在变成 S->b，c a->T，c a->b，d-c ZOJ2314ReactorCooling_网络流-个人编程笔记

一道网络流题目和其相关套路：ZR2627紫罗兰

一道网络流题目和其相关套路：ZR2627紫罗兰本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132296366 http://zhengruioi.com/problem/2627 Trick1：二分套网络流首先可以对原图建模中间拆点是为了两对棋子走到同一个格子上然后我们发现每条边除了容量还有一个边权，而我们的目标是求出每一个流量下的最小边权对于网络流中出现边权最值问题，可以进行二分。二分过程时枚举最值，然后保留可行边，来跑网络流 T...

数据加载中