关于ISAP的反向BFS的疑惑

P3376 【模板】网络最大流

Bodhi @ 2023-08-12 08:37:57

我举了一个这样的例子： ``` 5 5 1 4 1 2 10 2 3 20 3 4 10 1 5 10 5 4 20 ``` 可以发现，正着跑的确无法跑出正确的结果，但是不知道这其中的原理希望大佬帮我解答一下(〃'▽'〃)

by ShanireZ @ 2023-08-13 15:53:13

正着跑的是起点到所有点的最短路，反着跑的是所有点到终点的最短路

by Bodhi @ 2023-08-13 22:40:11

@ShanireZ 所以可以说这一次反向BFS 就是通过标记图层来帮助DFS找图的连通性的嘛