网站首页
编程语言
数据库
系统相关
其他分享
编程问答
1970G3
2024-08-22
Solution - Codeforces 1970G3 Min-Fund Prison (Hard)
时间\(\mathcal{O}(\frac{n\sqrt{n}\logn}{\omega})\)空间\(\mathcal{O}(\frac{n\logn}{w})\)的爆标做法。首先无解当且仅当图联通且无割边。首先考虑加边的贡献。一个比较直观的感受就是只会尽可能少的加边,即加边到整个图连通。证明考虑删掉的边。如果加多了边导致删