问题标签 [network-flow]

我在二分图问题中遇到了最大匹配问题。问题是这样的：

给定一个有 m 个圆孔的板和一组 n 个圆盘。孔编号为 h ₁ , ..., h _m，圆盘编号为 d ₁ , ..., d _n。

我们有一个 m 行 n 列的矩阵 A。_{如果 h i}可以拟合 d _j（即 h _i的直径≥ d _j的直径），则 A[i][j] = 1 ，否则为 0。

鉴于任何孔最多只能包含一个圆盘的条件，我需要找到最大的孔盘拟合配置。

我读过这个问题可以建模为网络流量问题，但不能完全遵循。有人可以解释如何做到这一点吗？另外，是否有任何我可以查看的 C 代码？

我试图在有向未加权图中找到不同 st 削减的数量。在一篇文章Enumeration in Graphs p 中。45 我找到了列举这些削减的好方法（第 7.3 节）。如果我只对此类削减的数量感兴趣并且我实际上不需要枚举它，是否可以使用更快或更简单的算法？

我正在使用的 st cut 的定义如下。我们有一个有向图，其中两个顶点标记为S和T。Cut 是图的最小边集，通过删除这些边，将不再存在从顶点S到顶点T的路径。

我有成本矩阵 C 的分配问题，例如：

21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31

其中 C[i][j] 表示工人 i 完成工作 j 的成本。

如何使用网络流算法解决这个问题？我欢迎任何提示。

如果所有路径的长度相同，如何选择Edmonds-Karp 算法的起始路径？在这种情况下，最大流量根据路径顺序决策而变化。

我很难理解来自 CLRS 的以下引理：

_{设 G 是一个流网络，s 和 t 是源和汇节点，f 是从 s 到 t 的预流，h 是 G 上的高度函数。那么在残差图 G f}中没有从 s 到 t 的增广路径.

为什么是这样？

在谈到 时computing network flows，算法设计手册说：

传统的网络流算法基于增广路径的思想，反复寻找从 s 到 t 的正容量路径并将其添加到流中。可以证明，当且仅当它不包含增广路径时，通过网络的流是最优的。

我不明白是什么augmenting paths。我用谷歌搜索，发现：

• Wolfram 中的增强路径

• Wiki 中的流网络

但他们都引用了上面的报价。

谁能真正清楚地解释什么是 a augmenting path？

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

我在最大流图中将其转换如下：如果收入（节点）> 0 从源-> 节点添加一条边，否则从节点-> 接收器添加一条边，我为优先约束创建了一个无限容量的 egde

如何在有向图中找到从源（S）到汇（S）的所有可能路径？

给定一个无向图 G=(V,E)，每个节点 i 都与“Ci”个对象相关联。在每一步，对于每个节点 i，Ci 对象在 i 的邻居之间平均分配。经过K步，输出对象最多的前5个节点的对象个数。

这是一步中发生的一个示例：
A 的对象被 B 和 C 平均分配。B
的对象被 A 和 C 平均分配。C
的对象被 A 和 B 平均分配。

一些约束：|V|<10^5, |E|<2*10^5, K<10^7, Ci<1000

我目前的想法是：用一个矩阵来表示每一步的转换。这个问题转化为矩阵幂的计算。但是考虑到|V|，这个解决方案太慢了。可以是 10^5。

有没有更快的方法来做到这一点？

给定一个有向加权图，如何找到所有顶点对之间的最大流量（或最小边切）。
天真的方法是简单地调用像 Dinic 的Max FlowO((V^2)*E)算法，其复杂性是，对于每一对。
因此对于所有对它都是O((V^4)*E)。

是否有可能通过一些优化O((V^3)*E)来降低复杂性？O(V^3)