can we find an algorithm which computes (in linear-time) the maximum flow for tree-like networks, that is, for networks such that the removal of the sink (and its associated edges) leaves a tree.
问问题
847 次
2 回答
2
是的,只需运行以下内容:
maxf(s) {
if (s == sink) return s.in_capacity;
ret = 0;
foreach(c in children(s)) ret += maxf(c);
return min(ret, s.in_capacity);
}
使用 s 等于源的初始调用(我们假设源的 in_capacity 为无穷大)。
于 2010-11-23T04:17:25.123 回答
0
Ford-Fulkerson 是 O(E*f),其中 E 是边数,f 是最大流量,如果您的问题中 E 或 f 有一个恒定的上限,这将被认为是线性的。
于 2010-11-22T23:49:46.870 回答