申请重新提交 P3376 网络最大流题解
  • 板块工单反馈版
  • 楼主学委
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/10/10 18:34
  • 上次更新2023/10/27 07:58:47
查看原帖
申请重新提交 P3376 网络最大流题解
49474
学委楼主2022/10/10 18:34

我在未重新提交审核 P3376 网络最大流 的题解时,突然收到通知说我的题解“审核失败”并被撤下。原因为“未添加当前弧优化”。

但当前弧优化是一个负优化!当我们遍历完 cur[u]cur[u] 之前的边,仅仅意味着从上一层某一个点走过来的路径无法再增广,然而在当前分层下,这个点可能从上一层另一个点走过来继续增广。这个优化将会推迟一部分增广到后一次分层。

实践:

158ms158ms 为加了“当前弧优化”的评测,而 86ms86ms 为不加该优化的评测。可见原代码拥有更高效率。

原题解发布于 2018 年,从评论区看,帮助了不少同学,并收获 600 多赞。我刚刚修改了原题解并通过理论和实践指出了当前弧优化的错误。然而当前 P3376 题解区已经无法重新提交题解。现在置顶的题解仅 100 多赞且运用了错误的当前弧优化。

请审核员重新考虑一下将该题解放回 P3376 的题解区,提前致谢。

原题解链接如下:https://www.luogu.com.cn/blog/cicos/Dinic

2022/10/10 18:34
加载中...