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