performance - 计算最小值 - 使用 maxflow 算法在有向加权图中进行切割

Question

我已经使用 ford fulkerson 算法计算了最大流量，现在我想实现需要计算最大流量的项目选择问题。不。可行的项目。我需要找到一个 min.cut 包含没有。具有最大利润的可行项目。找到最小值的算法应该是什么。在知道图中的最大流量后切割*。*我如何使用最大流量来确定包含即不包含的切割。贡献最大流量的节点数量。我需要选择最佳节点集，以使收入最大化。在我的应用程序中，每个节点都与收入相关联，它也可以是正数也可以是负数。并且也有优先约束，例如，如果选择 a 而不是 b&c 也必须选择 谁能告诉我如何实现这个吗？

---

我已将其转换为最大流图，如下所示:如果收入(节点)>0 从 source->node 添加一条边，否则从 node->sink 添加一条边，我已经为优先约束创建了无限容量的边

Answer 1

Ford Fulkerson 有点像元算法，因为它可以通过多种不同的方式实现(Edmonds-Karp 是 FF 算法的实例)。如果不知道您以何种方式实现它或您拥有什么信息，您的问题很难回答。

理想情况下，您正在使用某种残差图在算法中进行某种类型的广度优先搜索。当你这样做时，当你的 BFS 找不到接收器时，算法应该停止。一旦发生这种情况，您的切割的第一组是您能够使用 BFS 找到的所有节点，另一组是您找不到的所有节点。

如果您使用的是算法的标记版本，则形成切割的集合是标记集和未标记集。

希望对您有所帮助。诚然，您的问题对我来说有点难以解析。如果您在这里找不到足够的帮助，我会提供与 matcheek 相同的建议(如果您有那本书，请查看维基百科或 CLRS)。