问题标签 [max-flow]

我正在寻找一种算法，当一个给定的两个节点's'和't'在一个未处理的图中，找到最小切边，它将图分成两个A和B，'s'将在A和't ' 将在 B.

我看到大多数人建议使用 Ford-Fulkerson 算法来完成这项任务，在这里。我在想是否可以使用 Dinic 的算法。由于 Dinic 的算法可以通过动态树来加速。因为我想以最快的方式找到最小切边。

哪种算法可以更快地在巨大的无向图中找到最小切边？

在研究这些算法的细节时，我想听听一些建议。

提前致谢

我正在从事医学图像分割，我想将模糊连通性算法与图形切割相结合，这个想法是用模糊连通性分割图像，背景和前景将用作图形切割算法的接收器和源，这个是我获取图形切割分割的种子坐标的代码

对于图形切割，我使用了来自File Exchange的算法

例如，我可以定义

但问题是如何像这部分代码源一样结合成本函数中的信息

它将超过矩阵大小

嘿，所以我有一个图，例如 3 条边进入一个节点，3 条边出来，但是如果一个特定的输入边有容量，我只需要激活输出边。例如，如果我们有：

A -> N

B -> N

C -> N

N -> N'

N' -> A'

N' -> B'

N' -> C'

如果 A 有流量，我只想流过 A'，如果 B 有流量等，我只想流过 B'。

基本上它是边缘 A、B、C 的容量限制器，我最初无法限制它们的容量。

假设这种情况发生多次，我如何将此约束添加到最大流量并解决给定图的最大流量图问题？

编辑：我最终也不能限制它们的容量，因为稍后会在图中使用 A'、B' 和 C'，所以我不能将 N 和 N' 移动到最后并在以后强制组合容量减少。

我有两个班级MaxFlow和MinMaxFlow.

MaxFlow使用 boost graph 从网络拓扑创建图：

MaxFlow维护一个局部变量g_，因为我们只需要一个实例来完成这里的所有工作。 如果我们失败了（将容量设置为 0）MinMaxFlow，则迭代图中的每条边以找到最小的最大流量：edge

现在的问题是，maxFlowAlgo基于g_类中的局部变量MaxFlow，当我在中创建新对象maxFlowObj时MinMaxFlow，调用maxFlowObj.maxFlowAlgo()将使用它自己的数据，这使得结果不可预测。所以我的问题是：如果方法在中使用局部变量，我如何使用maxFlowAlgo属于MaxFlow第二类的方法（如） ？MinMaxFlowMaxFlow

更新：我发现问题出在boost::boykov_kolmogorov_max_flow，我使用捆绑属性并将容量属性映射传递给它，但是这个算法不仅会修改容量属性映射，还会修改我原来的边缘容量变量！现在的解决方法是我必须在运行算法之前存储容量值并在它之后恢复它们。应该不会修改原来的成员吧？

给定一棵无向树，其N顶点编号从 1 到 N。每棵边树都有一定的容量。求所有可能的顶点对之间的最大流量之和。在任何两个顶点之间只存在一种方式。
求所有可能的顶点对之间的最大流量之和。

例如：在具有 3 条边的给定树中，
1 2 5
2 3 6
节点 1 和节点 2 之间的边容量为 5，节点 2 和节点 3 之间的边容量为 6。
Output - 32

(1,2) = (2,1) = 5
(1,3) = (3,1) = 5
(2,3) = (3,2) = 6
因此输出为(5+5+6)*2 = 32

我的方法-

1. Sort基于 edge_capacity 的边

2. While edge_listis not empty: 以最小容量移除边

   • 计算该边上left的节点数。right对节点数进行 DFS
   • 将 ( left_count* right_count* edge_capacity) 添加到答案中。

3. 返回answer*2。
   

时间复杂度为 O(n ² )。该解决方案提供 TLE。
我们如何进一步降低时间复杂度？

我的代码-

链接到原始问题 - 树上的 Spoj-Flow

更新

约束——

1. 测试用例数量 - 10
2. 1 <= N <= 10 ⁵ （每个测试用例中的顶点数）
3. 每个边缘的容量将是非负的并且不超过 10 ⁶。
4. 所有测试用例中的顶点总数将小于 5*10 ⁵。

给定 G = (V,E) 中的两个顶点 u 和 v 以及一个正整数 k，描述一个算法来判断是否存在从 u 到 v 的不相交边路径。如果决策问题的答案是肯定的，描述如何计算一组 k 边不相交的路径。

解决方案：运行从 u 到 v 的最大流（给图 G 中的所有边的权重为 1，以便一条边只能是从 u 到 v 的一条路径的一部分）并获得流的值。如果流的值为 k，那么我们对决策问题的答案是肯定的。

现在为了找到所有这样的路径，通过从 u 执行 BFS 来找到最小切割，因此我将拥有顶点分区，这会将顶点分成 2 个集合，每个集合在最小切割的每一侧。

然后我是否需要再次执行从 u 到 v 的 DFS，以查找仅具有这些顶点的所有路径，这些顶点存在于我从最小切割中获得的两个分区集中。

还是有其他更清洁的方法？得到所有k条边不相交的路径。

所以我计算出最大流量为 10，因此意味着最小切割也为 10，但是我如何在此图像上绘制最小切割 10？

我不确定我是否对 mincut 有误解，但我已经使用 edmond-karps 编写了一个 mincut 算法，然后是流网络上的 BFS。

如果我告诉它从 A 到 B 做一个 mincut，它会起作用，因为剩余流 A->B = 0，所以它产生集合 {A}，切割为 A->B (1)。

但是，如果我告诉它从 B 到 A 做一个 mincut，它不会增加任何边（因为 C 没有边），所以结果集是 {C}，有一个 B->丙（2）。

在我看来，我可能会以两种方式中的一种方式误解这一点。首先，从 B 到 A 的 mincut 可能是正确的，因为只计算 B 集合中的边，而不是边（意味着 mincut 是在询问“不允许 B 连接到 A 的最小值是多少”，而不是“将图形分成 2 个分区的最小值是多少）。

或者，如果您被要求在流网络上查找 mincut（一般的 min-cut，我目前正在使用“选择任意源，尝试所有其他节点”方法），它必须要求在两个方向上的流量相等任何边缘。

鉴于本文中描述的 Push-Relabel Graph Cut 算法，我希望执行二值图像分割。我的问题是关于图形的初始化。

当将图像表示为具有格结构 (MRF) 的图时，通常会根据标准的一元和成对项能量函数来表述问题，如本文第 3 节等式 1所述，其中一元项是数据能量和成对项模拟某些邻域的平滑度。

我正在努力将这个 MRF 优化公式与链接文章中的最大流算法公式联系起来。据我了解，相邻节点之间的容量可以用一些距离函数（基于空间距离和强度值）来表示，例如本文中的第 2 节等式 7 。然而，目前尚不清楚如何将先验知识纳入图初始化，例如种子点的初始分布。

在更高的层次上，给定一张带有一些与背景或对象类相关的标记种子点的图像，如何初始化流图以使最大流可用于执行二进制分割？

餐饮问题：
几个家庭一起出去吃饭。为了增加他们的社交互动，他们喜欢坐在桌子旁，这样同一个家庭的两个成员就不会坐在同一张桌子上。假设晚餐队伍有p家庭，并且i第 th 家庭有a(i)成员。此外，假设有q可用的桌子，并且j第 th 桌子的座位容量为b(j)。

问题是： 我们可以坐在桌子上的最大人数是多少？

编辑：这个问题可以通过创建图形和运行最大流量算法来解决。但是如果我们有 2*10^3 个顶点，使用 Dinic 算法，全局复杂度是 O(10^6*10^6) = O(10^12)。

如果我们总是以贪婪的方式坐在较大的群体前面。复杂度为 O(10^6)。

所以我的问题是：

1）这个问题的贪婪方法有效吗？

2）解决这个问题的最佳算法是什么？