关于dinic的细节实现问题
查看原帖
关于dinic的细节实现问题
413147
feicheng楼主2021/7/7 20:56

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

2021/7/7 20:56
加载中...