rt,我今天在敲dinic的时候,在 dfs 的时候写多路增广时,如下两种写法的差距竟高达400ms,百思不得其解。
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 ;
}
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