警钟撅烂

P3376 【模板】网络最大流

_saltFish_ @ 2024-02-23 09:55:06

如果你写的是 ISAP 并且只 A 了 #2#11#12,那么请检查你在 dfs 时是否在当前节点流量已经为 0return sumflow;

具体的是因为 ISAP 会将无法再增广的点深度增加 1 后续再考虑增广这个点能到达的更深的点。如果还可能增广(在代码中体现的就是 if(flw==0) 我的代码中 dfs 到达当前点流量是 flw)就直接退出。否则就会每访问一个节点都会将这个节点往下推一层,导致剩下的流量浪费。

在这里给出一个针对这个错误的 hack:

4 4 1 4
1 2 1
1 3 1
2 3 1
3 4 114514

正确的答案是 2,如果是上述错误,应该会输出 1


by bryce @ 2024-02-23 10:16:25

@saltFish %%% 机房大佬


|