首页 > 代码库 > [codevs 1995]黑魔法师之门(并查集)
[codevs 1995]黑魔法师之门(并查集)
题目:http://codevs.cn/problem/1995/
分析:脑补一下满足题目要求的子图肯定就是环……于是题目就变成了不断加边求环的个数。看起来有点麻烦……但是环的实质是几个小环组合起来的……所以我们只需要知道最基础的环的个数就行了,根据二项式定理那么就是2^(最基础的环的个数)-1。还是不好做啊!!!!!!
没关系……并查集来了……
假设对于第i-1操作后,最终答案为ans,那么对于第i次操作,分为两种情况
①加入这条边后,没有出现新环,那么说明对结果无影响,结果还是ans
②加入这条边后,出现了新环。那么对于以前的ans种环,我们可以帮这个新环放进去组合作为新的环,于是ans*2,但是要注意我们还多了一个新的基础的环,所以ans=ans*2+1
于是完美解决……
[codevs 1995]黑魔法师之门(并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。