首页 > 白金元首与独舞

苟且的狮子

发表于 2020-08-09 14:28:28

矩阵树这题不错，又学到了一个知识点。欸嘿嘿。题意：分析：我们来看这道题：首先，我们不妨把外面虚拟成一个点。那么问的就是，矩形中的所有点能否到达外面的点。这时，我们想想。如果能都联通的话应该会是什么情况？首先肯定有一些点本来就联通。我们以虚构的最外面的点出发，进行深度优先搜索。肯定能将展开全文

小毅儿

发表于 2020-09-08 18:23:12

//这道题是矩阵树定理中：给出有向图和其中一个点，求以这个点为根的生成外向树个数 /* 矩阵树定理：有向图有根树的情况去掉所有自环，主对角线上第i行第i列是i这个点的出度，剩下的是邻接矩阵取相反数。然后求的是删掉根节点所在行列式的余子式的行列式 */ #include <cstd 展开全文

科员

发表于 2023-04-13 12:58:24

这道题是到矩阵生成树的变形题我们不妨假设能走出去的为连通块1 把平面上的位置当成一个点，它永远指向一个点。而外部也相当于一个点而它不指向任何一个地方，这就是一颗有向生成树 .相当于其他树的根。我们可以讨论它能指向哪颗树，即可这样就抽象出矩阵生成树的板子了

查看本题

查看本题讨论

等你来战

查看全部

相关比赛