社区讨论

编了个假做法,然而想不出反例

P3225[HNOI2012] 矿场搭建参与者 6已保存回复 12

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
12 条
当前快照
1 份
快照标识符
@loccnmw2
此快照首次捕获于
2023/10/30 11:37
2 年前
此快照最后确认于
2023/11/04 23:19
2 年前
查看原帖
我的做法是把所有缩点找出来之后,无视所有缩点,统计剩下的联通块数量和大小,最少的出口数即为联通块个数,总方案就是这些大小之积。
因为每一个联通块中都至少要有一个出口,以防与该块相连的割点倒塌,所以最小方案就是在每个联通块都设置一个出口。
我自己想了很久都找不出反例,希望大佬能指出错误。

回复

12 条回复,欢迎继续交流。

正在加载回复...