知识卡片
预流允许中间顶点暂时溢出
推送重标记算法运行时允许中间顶点流入大于流出,形成预流和溢出顶点;
溢出点向高度更低且有残余边的邻点推流,无法推时升高高度,直到无非汇点溢出。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第24章 最大流 · 查看原书依据
A class of algorithms known as push-relabel algorithms, due to Goldberg [185] and Goldberg and Tarjan [188], takes a different approach from the Ford-Fulkerson method. Push-relabel algorithms allow flow
参考来源
- 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[60000,65000))。
- 结论依据:章注解释预流、溢出、高度、推送与重标记的机制。
- 原始内容:A class of algorithms known as push-relabel algorithms , due to Goldberg [ 185 ] and Goldberg and Tarjan [ 188 ], takes a different approach from the Ford-Fulkerson method. Push-relabel algorithms allow flow