知识卡片
正向残余容量是未用额度
- 对原边
(u,v),c(u,v)是容量,f(u,v)是当前流量。若f(u,v)<c(u,v),残量网络保留同向边,残余容量为c_f(u,v)=c(u,v)-f(u,v); - 边已满载时残余容量为 0,因而不出现在残量图中。
补充教学演示:容量为 10、已送 6 单位流时,同向还可增加 4 单位;若已送到 10,便不能再沿同向增广。残量容量描述的是“在当前流基础上还能怎么改”,并不是原网络的新容量。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第24章 最大流 · 查看原书依据
If that value is positive, that edge goes into Gf with a “residual capacity” of cf (u, v) = c(u, v) − f (u, v). The only edges of G that belong to Gf are those that can admit more flow. Those edges (u, v)
参考来源
- 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[15000,20000))。
- 结论依据:原文给出同向残余容量及零容量边不保留的条件;数值代入为补充教学演示。
- 原始内容:If that value is positive, that edge goes into G f with a “residual capacity” of c f ( u , v ) = c ( u , v ) − f ( u , v ). The only edges of G that belong to G f are those that can admit more flow. Those edges ( u , v )