在 运行 最大流算法之后，在流网络中找到所有在某个最小切割中的边

Question

设 G=(V,A,s,t,U) 为流网络。假设我们已经获得了最大流量。有没有一种快速算法可以找到某个最小切割中的所有边？

我知道如果x是最大流，那么我们可以在残差网络G(x)中找到从源s可达的顶点集合S ，以及 T 我们可以到达 t 的顶点集。因此，S 及其补码是最小割。此外，T和它的补集也形成了一个最小割。

如果不幸的是 T 不是 S 的补集，则最小割不是唯一的。我想知道是否有一种好的方法来确定末端既不在 S 也不在 T 的边缘是否属于最小切割。

Answer 1

每个圆弧 u-->v 属于某个 s--t min cut 当且仅当

1. 没有从u到t,
的剩余路径
2. 没有从s到v的剩余路径，并且
3. 没有从u到v的剩余路径。

为了证明 if 方向，考虑由残差路径从 s 或 u 可达的顶点组成的切割，即 s--t 由 (1) 切割，具有剩余容量为零，因此是 s--t 最小构造削减，并且包含 u-->v 由 (2) 和 (3)。

为了证明唯一的方向，我们可以使用包含 u-->v 的 s--t 最小切割来证明，对于从 u 到 t 的每条路径，从s到v，或从u到v，路径中的某些弧是非残差的。

这会让您很容易地到达 O(n m) 时间。也许这就足够了——如果还不够好，有一篇关于回答离线可达性查询的文献可能会有用。