问题标签 [max-flow]

我试图从研究论文中描述的给定图像中提取头发，使用能量最小化的概念，能量函数取决于先验概率和 YCrCb 颜色似然直方图。能量函数定义为：

data (x)=−∑(log(I(x)|x)+logsel (x)) [先验概率模型]

平滑 (x) = ∑ (x ≠x )exp(-||(x)−(x)||^2/) [之前的 YcrCb 颜色模型]

我对如何标记给定图形感到困惑（图像的像素被视为图形的节点）。我尝试使用以下方法标记图表，但结果与预期不符：

在图中我使用的节点之间添加权重时：

我想问题在于，max_val_weight-source因为将值更改为一些较低的整数会给我带来相对较好的结果，但这不是正确的做法。

将 eSmooth 的值更改为 0 也不会影响输出？

如果有人能对这种情况有所了解，我将不胜感激。

如何解决图中的某些边必须具有流 = 3n 的最大流问题，其中 n 是非负整数？换句话说，你如何施加某些边缘必须具有可被 3 整除的流量的约束？例如，这些边可能有流 0、3、6、9 ......但可能没有流 1、2、4、5 ......理想情况下，我想要一种方法来计算这样的图上的最大流和也是最大流量配置中每个边缘上的流量。

有人可以解释一下连续最短路径（SSP）是如何对福特-富克森算法进行概括的吗？我在一些论文和网站以及 Wikipedia 页面中发现了最低成本流问题的说明。但他们都没有比那句话更进一步，也没有解释它们到底有什么不同。任何帮助将不胜感激。谢谢。

我有一个图 G，它是一个有向且强连通的图，我被要求找到所有顶点对的最小割，这意味着图中的每一对 S 和 T。这应该在 O(m ² × n ² ) 时间内完成。

我想出的最好的方法是将所有顶点视为 S，并且对于每个 S，将所有其他顶点视为 T，并且对每个顶点运行 Ford-Fulkerson 算法，然后找到最小割。但如果我没记错的话，这个算法的复杂度是 O(m ² × n ² × C)。

我怎样才能在 O(m ² × n ² ) 时间内完成这项任务？甚至可能吗？

您有一个n x n网格，其中有n行和n列。对于每一列j，您将获得一个数字 C j，对于每一行i您将获得一个数字 R i。您需要在网格上标记一些点，这样：

• 每行标记点数最多为 R i；
• 每列的标记点数最多为 C j；
• 您标记满足最后两个约束的最大点数并返回此点数。

输入为：n（网格的维度）；R i的序列和 C j的序列。

例如在这个网格中，回报是 34 例子

在线性时间内找到一个算法：O( n ) 或 O( n log( n )) 并带有演示。我找到了 Max-Flow alg 的解决方案。但是复杂度太高了。

问题是：

对于 (a) 似乎不正确，我们可以找到一个流量在不饱和的情况下增长的示例。

对于（b）这似乎是正确的，但我不知道如何证明它。也许是因为最小切割最大流量定理，它在最小切割上，所以它必须增长。

对于 (c) 它似乎是错误的。流量增加是因为 e 发生了变化，但 e 可能没有正好增长 5。

如下所示，给出了具有源和汇的二部图。每条边的容量为 1 个单位： 来源：GeeksforGeeks

我试图找到从源到接收器的最大流量。一种方法是使用适用于所有图的最大流量问题的 Ford-Fulkerson 算法。我找到了一种简单的方法来找到最大流量（太简单了，不正确！）我无法在该方法中找到任何错误。

方法 ：

c1 = 计算具有非零边数的顶点数，在具有出边的顶点列表中。

c2 = 计算具有非零边数的顶点数，在具有传入边的顶点列表中。

最大流量将是这两个数字中的最小值，即 min(c1,c2)。[因为任何路径都需要一个来自传出顶点列表的顶点，而另一个来自传入顶点列表。]

任何帮助，将不胜感激。

给定一个加权有向图，我们希望找到全局最小割——也就是说，如果删除一组边，将图分成两半，并且与任何其他此类割相比，它们的总权重最小。

现在，尽管以下似乎可行，但有人告诉我推理是错误的。但坦率地说，我不明白他是如何确定的，我不确定他有多确定：

U,V考虑由全局最小割（即 st-割，其中s in U, t in V）分隔的节点集。注意：我们不关心从V到的边缘U。

对于任何u in U, v in Vm uv-cut 不能小于s-t-cut，否则，st-cut 不会（全局）最小。出于同样的原因，两个顶点之间的切口u或两个顶点之间的切口V可以更小。

另一方面，uv-cut 也不能​​更大，否则，它需要包括一些U->V不属于 st-cut 的边缘，这意味着 st-cut 根本没有切割。

因此，s任意固定并遍历所有其他顶点就足够了x。s是 in U，则 sx-cut 对应于全局最小值 if xis in V，或者 xs-cut 对应于 if sis inV和xis in U。如果它们都是同一集合的一部分，则切割将至少与全局最小值一样大（但可能更大）。

因此，我们最终将通过计算两者来找到全局最小值，并跟踪迄今为止遇到的最小割。

这对我来说似乎很有意义。我错了吗？如果是这样，为什么？

我需要使用

BGL (v 1_60_0) 中可用的功能。如文档中所述，

表示网络的有向图 G=(V,E) 必须扩充为包含 E 中每条边的反向边。也就是说，输入图应该是 Gin = (V,{EU ET})。[...]CapacityEdgeMap 参数 cap 必须将 E 中的每条边映射到一个正数，并将 ET 中的每条边映射到 0。WeightMap 必须将每条边从 E 映射到非负数，并将每条边从 ET 映射到 -weight of它的反向边缘。

我有一个简单的函数，对于添加到图中的每条边，添加一条具有上述容量和权重的反向边：

现在，该图包含反向边，并且它们具有负权重，这与我正在使用的算法的名称形成鲜明对比。结果，当我执行算法时，我得到了这个错误：

我究竟做错了什么？

有 N 块，每块的大小为 Ai。将一块大小为 x 的块和一块大小为 y 的块连接起来的成本是 abs(xy)。加入所有部分的最佳方式是什么？可以使用最大流算法解决吗？