问
  • 板块灌水区
  • 楼主Komomo
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/11 20:43
  • 上次更新2023/11/3 04:23:57
查看原帖
问
376919
Komomo楼主2023/8/11 20:43

对于【模板】网络最大流的第二篇 ISAP的题解 在 dfs 的最后一段有这么一段代码:

    --gap[dep[u]];
    if(gap[dep[u]]==0)dep[s]=n+1;//出现断层,无法到达t了
    dep[u]++;//层++ 
    gap[dep[u]]++;//层数对应个数++
    return used; 

但是在 oi-wiki 是这么讲的:

而 ISAP 还存在另外一个优化,我们记录层数为 ii 的点的数量 numinum_i,每当将一个点的层数从 xx 更新到 yy 时,同时更新 numnum 数组的值,若在更新后 numx=0num_x=0,则意味着图上出现了断层,无法再找到增广路,此时可以直接终止算法(实现时直接将 dsd_s 标为 nn),该优化被称为 GAP 优化。

本人觉得下面解释更加合理,所以题解中的代码这么写的依据是什么,求助

2023/8/11 20:43
加载中...