BZOJ 4596 [Shoi2016] 黑暗前的幻想乡

发布于 2017-07-05  211 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4596

题意:一个无向图,每个公司可以修一些边,求每个公司恰好修一条边且修的边集为原图的一个生成树的不同方案数


看到数据范围很小,可能需要枚举子集

求生成树可以直接矩阵树定理,那么如何满足每个公司恰好一条边呢?

可以先从两个公司的情况开始考虑:显然为了修建一个生成树,只可能两个公司各一条边,或者一个公司修两条边。分别记为 x,y

不去考虑公司的限制,可以求出一次生成树的个数 S,显然的是 S=x+y

我们希望得到的答案是 x,那么 y 如何减掉呢?分别枚举两个公司不修的情况,那么求出的生成树一定是另一个公司修了两个的情况:都减掉就好了。当然还有两个公司都不选的情况被减重了,需要加回来,尽管在这个简单的问题不存在这种情况

所以对于 n 个公司的情况,也是一样的容斥即可

为什么跑了 16s 啊 T.T 完美垫底 是哪里写的不对吗

 


一个非常弱的准退役OIER