推流重新标记算法

Question

V wrt中顶点的有效标签。预流x是满足以下条件的函数d :v -> Z：

ds =n^dt=0

对于所有属于E: dv <= dw +1的(v，w)

假设我们有4个顶点，包括(s和t)

然后我们有ds =4

根据有效的标签，我们应该有dv <= dw+1，但是对于来自's‘的边，它是无效的，因为4 <= 1是false。这个逻辑不是唯一的来源吗？

我理解得对吗？请纠正我。

感谢您的时间和帮助

Answer 1

您对有效标签的定义很接近，但并不完全正确。

你声称对属于E的所有(v，w)，dv <= dw +1。

然而，这实际上只需要对于属于R的所有(v，w)为真，其中R是残差边缘。

剩余边缘是指当前流量小于边缘上的容量的边缘。

在topcoder上有一个很好的解释。

考虑下图：

​

​

在边上的标签(如2/3)中，第一个数字表示当前流量，第二个数字表示边的容量。

节点上的数字给出了每个节点的高度函数d。

绿色边是剩余边，因为它们有空闲容量。

因此，要检查高度约束，我们只需检查S->A边和B->T边。