[codevs 1995]黑魔法师之门（并查集）
2024-10-10 17:53:15
题目：http://codevs.cn/problem/1995/
分析：脑补一下满足题目要求的子图肯定就是环……于是题目就变成了不断加边求环的个数。看起来有点麻烦……但是环的实质是几个小环组合起来的……所以我们只需要知道最基础的环的个数就行了，根据二项式定理那么就是2^(最基础的环的个数)-1。还是不好做啊！！！！！！
没关系……并查集来了……
假设对于第i-1操作后，最终答案为ans，那么对于第i次操作，分为两种情况
①加入这条边后，没有出现新环，那么说明对结果无影响，结果还是ans
②加入这条边后，出现了新环。那么对于以前的ans种环，我们可以帮这个新环放进去组合作为新的环，于是ans*2，但是要注意我们还多了一个新的基础的环，所以ans=ans*2+1
于是完美解决……
最新文章
- 11.Configure Many-to-Many（配置多对多关系）【Code-First系列】
- [Prodinner项目]学习分享_第三部分_Service层(业务逻辑层)
- 关于C++string的长度陷阱
- Java笔记(十三)……面向对象III继承(inheritance)
- "解密"微信开放高级接口 企业如何应对
- WEB打印的几种方案
- 用VS Code体验调试.NET Core 2.0 Preview （传统三层架构）
- SQL Server 禁用扩展存储过程
- PAT1119. Pre- and Post-order Traversals
- app与手机其他软件交互测试
- Altium Designer (17.0) 打印输出指定的层
- mysql 字符串 拼接 截取 替换
- ubuntu18.04 安装mysql server
- video control
- sqlite 字符串拼接
- java BigDecimal实现精确加减乘除运算
- eclipse的thrift插件
- java 网站源码 六套模版 兼容手机平板PC freemaker 静态引擎 在线编辑模版
- OpenLayers 3 入门教程
- Asp.net Web Application 打开 SharePoint 2010 Site 错误 The Web application at could not be found