关于 Dinic 的当前弧优化

在一道题目中，我分别尝试了以下两种维护当前弧的方式：

方式 1

CPP

for(int i=cur[u];i!=-1&&ans<flow;i=e[i].nxt)
{
    cur[u]=i;
    int v=e[i].v;
    if(e[i].cap>0&&dis[v]==dis[u]+1)
    {
        int x=dfs(v,t,min(flow-ans,e[i].cap));
        if(x>0) ans+=x,e[i].cap-=x,e[i^1].cap+=x;
    }
}

方式 2

CPP

for(int &i=cur[u];i!=-1&&ans<flow;i=e[i].nxt)
  {
      //cur[u]=i;
      int v=e[i].v;
      if(e[i].cap>0&&dis[v]==dis[u]+1)
      {
          int x=dfs(v,t,min(flow-ans,e[i].cap));
          if(x>0) ans+=x,e[i].cap-=x,e[i^1].cap+=x;
      }
  }

代码的其他部分没有任何差异。

然而，方式 1 获得了 AC，方式 2 获得了 TLE。

有大佬能解释一下这两种写法有什么区别吗？

关于 Dinic 的当前弧优化

讨论操作

回复

相关推荐

关于 Dinic 的当前弧优化