algorithm - 推流重标记算法

Question

V wrt 中顶点的有效标记。预流 x 是一个函数 d[.] : V -> Z 满足：

d[s] = n ^ d[t] = 0

对于所有 (v,w) 属于 E ： d[v] <= d[w] + 1

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

那么我们有 d[s] = 4

根据有效标签，我们应该有 d[v] <= d[w]+1，但是对于来自 's' 的边，它是无效的，因为 4 <= 1 是假的。难道这个逻辑不仅是来源吗？

我理解正确吗？请纠正我。

感谢您的时间和帮助

Answer 1

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

您声称对于属于 E 的所有 (v,w)，d[v] <= d[w] + 1。

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

剩余边缘是电流小于边缘容量的边缘。

topcoder有一个很好的解释。

考虑这个图表：

在边上的标签（例如 2/3）中，第一个数字给出了当前的流量，第二个数字给出了边的容量。

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

绿色边缘是剩余边缘，因为它们具有备用容量。

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