StarPatrick @ 2023-05-03 20:26:52
for (int p=cur[i];p<v[i].size();p++) {
cur[i] = p;
if (v[i][p].u&&dis[v[i][p].i]==dis[i]+1) {
ll flow = dfs(v[i][p].i, min(u, v[i][p].u));
u-=flow, all+=flow;
v[i][p].u-=flow;
v[v[i][p].i][v[i][p].back].u+=flow;
if (!u) return all;
}
}
这个59ms
for (int p=cur[i];p<v[i].size();p++) {
cur[i] = p+1;
if (v[i][p].u&&dis[v[i][p].i]==dis[i]+1) {
ll flow = dfs(v[i][p].i, min(u, v[i][p].u));
u-=flow, all+=flow;
v[i][p].u-=flow;
v[v[i][p].i][v[i][p].back].u+=flow;
if (!u) return all;
}
}
这个659ms,仅仅改了这一个地方
cur[i] = p+1;
理应说来应该更快啊,为啥慢了好多?
by reveal @ 2023-05-03 20:30:47
@cqbzzqw 因为当前边并不一定是断开的,可能推过来的流用完了导致退出了,但是此时当前边仍可以推流。
考虑后面为什么要写 if (!u) return all;
就是为了不会错误的跳边,不然这一句为什么不写循环条件里。
by Miraik @ 2023-05-03 20:33:12
@cqbzzqw 你这条边这次也不一定流满,那你这一轮不再访问它就会导致轮数增加
by TulipeNoire @ 2023-05-03 20:36:55
对的,我也是这样的,十分疑惑。
by Others @ 2023-05-03 20:44:40
@cqbzzqw 1~n-2 与 n-1 连边,流量1,n-1与n连边流量n-2,这样你每 dfs 到 n-1 一次,只用了一个流量,就会退回去(cur 超过了 size),然后搞一遍分层。
你说挂不挂。
by Others @ 2023-05-03 20:45:33
哦,还得有个 0 给 1~n-2 流量。
by StarPatrick @ 2023-05-03 21:00:42
@DitaMirika @reveal @Others 悟了,谢谢大佬们