首页 > 试题广场 >

(最大流的更新)设G=(V,E)是一个源结点为s汇点为t的

[问答题]
 (最大流的更新)设G=(V,E)是一个源结点为s汇点为t的流网络,其容量全部为整数值。假定我们已经给定G的一个最大流。
a.如果将单条边(u, v)∈E的容量增加1个单位,请给出一个O(V+ E)时间的算法来对最大流进行更新。
b.如果将单条边(u,v)∈E的容量减少1个单位,请给出一个O(V+E)时间的算法来对最大流进行更新。 

这道题你会答吗?花几分钟告诉大家答案吧!