问题标签 [max-flow]

给定一个流网络 G = (V,E)，其源为 s，汇为 t，边 e = (u,v)，描述一种算法来确定边 e 是否与某个最小割 (S,T) 相交。

我的第一个想法是计算最大流量 f，然后将 e 的容量减少一些 a > 0。然后我们检查残差图是否有从 s 到 t 的路径（这意味着我们可以进一步增加流量 f） .

现在，如果没有从 s 到 t 的路径，我们可以确定 e 不会越过任何最小割。

问题在于另一个方向。如果有一条从 s 到 t 的路径，那可能是因为我们在选择 a > 0 时不小心创建了一个新的最小割使 e 交叉。

那么如何选择足够小的 a > 0 呢？

opencv 有一个最大流算法的实现（GCGRAPH文件 gcgraph.hpp 中的类）。它在这里可用。

有谁知道这个类实现了哪个特定的最大流算法？

This is a part of an exam preparation. I know it has something to do with max-flow algorithm, but I'd be happy for a hint:

Let G=(V,E) an undirected connected graph, and let w:E->R a weight function, e an edge and k > 0. Describe an algorithm that determines whether we can remove at most k edges from the graph, so that e would belong to a minimum spanning tree of the new graph.

I think that a spanning tree is kind of a perfect matching. But how do I make it minimal that contains e and the right amount of other edges?

我正在对此进行编码，并且需要了解这两种不同算法的限制：1）容量必须是整数吗？2）图必须是非循环的吗？

谁能给点提示？

谢谢

我想知道 max-flow 和 min-cut 之间著名的二元性是否真的可以容忍无限的价值容量。这是一个似乎不是的简单示例：

源 s、汇 t、其他五个节点 a、b、c、d、e

s -> a: 容量 3

s -> b: 3

a -> c: \infty

a -> d: \infty

b -> d: \infty

b -> e: \infty

c -> t: 1

d -> t: 1

e -> t: 4

最大流量为 5。但是，没有容量为 5 的切割。这是因为无限容量迫使所有 a、b、c、d、e 属于同一集合/切割的一半（否则会有割集中的一个 \infty 权重）。

我正在从 topcoder 站点学习 push-relabel 算法：http: //community.topcoder.com/tc ?module=Static&d1=tutorials&d2=maxflowPushRelabel 我认为实现有问题。节点饱和时如何将多余的流量推回节点。例如：

在找到从 1 到 3 的最大流量时，在某一阶段我需要将流量从 2 推回到 1（因为 2 没有出边）。但在先进先出算法的代码实现中，第16行的循环从0 to G[u].size(). 既然 2 没有从 2 到 1 的任何边，它怎么能把流量推回到 1 呢？

如果需要，这是我糟糕的实现：

我们知道正常的背包问题具有伪多项式时间，因为 O(nW) 的运行时间。我想知道网络流的运行时间是否是伪多项式时间，因为使用 Ford-Fulkerson 算法的网络流的运行时间是 O(Cm)(m 表示边数，C 表示从起点离开的边的容量总和) ?

C1 城市愿意出售一些商品，而其他 C2 城市愿意购买一些商品（每个城市都可以出售或购买商品，但不能同时出售）。每个销售城市只能向一个城市销售商品，每个购买城市只能从一个城市购买商品。

您的目标是以最大化交换商品数量的方式连接自私的城市。

最难的是每个城市只能向/从一个城市出售/购买商品的限制。

我试图找到一个反例，但它似乎不存在。但是，也找不到证据。也许有人有什么想法？这是详细信息：

对于具有非零最大流量值的每个 st 流网络，都存在一条边，因此降低该边的容量将降低最大流量的值。这是真的假的吗？