关于dinic的细节实现问题

P3376 【模板】网络最大流

feicheng @ 2021-07-07 20:56:46

rt,我今天在敲dinic的时候,在 dfs 的时候写多路增广时,如下两种写法的差距竟高达400ms,百思不得其解。

1.写引用的写法

long long dfs(int x,long long sum) {
  if (x == t) return sum ;
  long long k,res = 0 ;
  for (int &i = now[x]; i && sum; i = nxt[i]) {
    const int v = to[i] ;
    if (dis[x] + 1 == dis[v] && val[i] > 0) {
      k = dfs(v,min(sum,val[i])) ;
      if (!k) dis[v] = inf ;
      res += k,val[i] -= k,val[i ^ 1] += k,sum -= k ;
    }
  }
  return res ;
}

2.不写引用的写法

long long dfs(int x,long long sum) {
  if (x == t) return sum ;
  long long k,res = 0 ;
  for (int i = now[x]; i && sum; i = nxt[i]) {
    const int v = to[i] ; now[x] = i ;
    if (dis[x] + 1 == dis[v] && val[i] > 0) {
      k = dfs(v,min(sum,val[i])) ;
      if (!k) dis[v] = inf ;
      res += k,val[i] -= k,val[i ^ 1] += k,sum -= k ;
    }
  }
  return res ;
}

可否有大佬解答一下这两种写法有何区别/kel


by Mars_Dingdang @ 2021-07-07 21:18:32

@飞丞 前者是当前弧优化,自动跳过已经增广过的边。

后者不修改 now 相当于没有优化啊


by feicheng @ 2021-07-07 21:25:50

@Mars_Dingdang 后者修改了 now,您可以仔细看下定义 v 的后面。另:后面的代码更快


by Reywmp @ 2021-07-07 21:49:09

直接地址符改快一些吧


by Reywmp @ 2021-07-07 21:49:57

感觉都差不多,主要是 Dinic 他这个循环量级太大了。


by Reywmp @ 2021-07-07 21:52:26

可能是你写法问题导致的差距


by zimujun @ 2021-11-18 15:38:53

?为什么我直接引用的挺快的

https://www.luogu.com.cn/record/49149869


|