[LuoguP4208][JSOI2008]最小生成树计数(最小生成树+矩阵树定理)

2021-01-16 14:12

阅读：718

标签：math alc find 数据分类复杂计数 define swap

[LuoguP4208][JSOI2008]最小生成树计数

题面

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。

分析

引理:同一个图的所有最小生成树中，边权相等的边数量相等

考虑Kruskal算法的过程,我们会按边权依次加入两端点不属于同一连通块的边。边权相同的边是连续加入的，因此操作等价于加入所有边权相同的边,然后消除所有简单环,不同的消环方式对应不同的生成树。消除一个简单环等价于删掉环中一条边。所以,无论怎么消环,最后剩余的总边数一定。

根据这个引理,我们可以求出每一种边权的选择方案，再乘起来得到答案。对于每种边权,我们将最小生成树上非该边权的边加到一个新图上,然后把每个连通块缩成一个点。之后将原图上所有边权为该值的边都加在新图上。新图的生成树个数即为答案,用Matrix-Tree定理求解。(其实这里的生成树个数和引理证明里提到的消环方案数是等价的)

可以证明复杂度为\(\Theta(n^3)\)

代码

#include
#include
#include
#include
#define maxn 100 
#define maxm 1000
#define mod 31011
using namespace std;
typedef long long ll;
int n,m;
struct DSU{
    int fa[maxn+5];
    int find(int x){
        if(fa[x]==x) return x;
        else return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        fa[find(x)]=find(y);
    }
    void ini(int n){
        for(int i=1;i

[LuoguP4208][JSOI2008]最小生成树计数(最小生成树+矩阵树定理)

标签：math alc find 数据分类复杂计数 define swap

原文地址：https://www.cnblogs.com/birchtree/p/13377158.html

上一篇：CentOS7为php7.2安装php-redis扩展(redis环境搭建二)

下一篇：网页批量打印成PDF，并按条件合并成大PDF、生成页码

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[LuoguP4208][JSOI2008]最小生成树计数(最小生成树+矩阵树定理)
文章链接：http://soscw.com/index.php/essay/42742.html

亲，登录后才可以留言！

[LuoguP4208][JSOI2008]最小生成树计数(最小生成树+矩阵树定理)

[LuoguP4208][JSOI2008]最小生成树计数

题面

分析

代码

评论

热门文章

推荐文章

最新文章

置顶文章