社区讨论

本题的神秘现象和解释

CF2029I Variance Challenge参与者 6已保存回复 5

讨论操作

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

当前回复
5 条
当前快照
1 份
快照标识符
@mhjnwkbz
此快照首次捕获于
2025/11/04 05:38
4 个月前
此快照最后确认于
2025/11/04 05:38
4 个月前
查看原帖
调试时偶然发现,对于样例的第二个小样例:
CPP
3 2 2
1 2 2
当你枚举操作区间总长度为 33 时,此时最优解为 22,操作方法是 [1,1],[2,3][1,1],[2,3]。但是跑不出来,只能跑出 66,因为第一次增广会操作 [1,3][1,3],后面就不对了。
但是网络流模型中是对的,因为建模允许出现空区间(SxTS\to x\to T)。
所以解释就是:这个网络流建模会出现空区间的情况,要是模拟费用流时不考虑空区间就会出现上述现象。
不过这不影响正确性,因为只需全局 +k+k 方差不变,等价于空区间,所以虽然当前漏考虑了但是后面还是会被算入。

回复

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

正在加载回复...