我正在尝试解决具有额外流量限制的最小成本最大流量问题。似乎经典的网络流算法无法处理这个问题。

这是一个例子：

假设我有一个二分图，左右之间的每条边都有一个成本。与经典的最小成本最大流量问题不同，在我的问题中，每条边的允许流量可以是（0 或 1）或（0 或 2）。如图（示例流程）所示（我没有绘制源和目标）。请注意，对于允许流量为（0 或 2）的边，不允许 flow == 1。

我不希望得到最佳解决方案，但需要在多项式时间内解决它。

我真的很感激任何建议/帮助。

谢谢！

令 G = (V,E) 是一个任意流网络，具有源 s 和目标 t 以及每条边 e 的正整数容量 c(e)。令 (S,T) 是关于这些容量的最小 st cut。现在假设我们将每条边的容量增加一，即所有边的 c_new(e) = c(e) + 1，那么 (S, T) 是否仍然是这些新容量 {c_new} 的最小 st 切？

我的直觉是，如果 G 包含不同容量的边，容量的增加可能会导致不同的最小切割。但是当所有边都具有相同的容量时，最小切割将保持不变。

我对么？如何证明这一点？

我知道我们可以使用网络流的福特富尔克森算法在二分图中找到最大匹配。但是是否有任何算法使用网络流概念并为非二分图提供最大（甚至最大）匹配？

我正在尝试使用有向图解决最小成本流问题的修改实例。具体来说，源和目标对是固定的，每条边都有单位成本但容量有限。我想最小化总和（流量）/边缘。我有两个与此相关的查询：

1. 如果每个流程从源到目的地都有一条路径，我应该如何进行？一种解决方案可能是使用最短路径算法（例如 Dijkstra），但只考虑可以完全适应流的路径。这可以通过迭代求解每个流并每次更新边缘容量来完成。我回顾了与最小成本和最大流量问题相关的文献，它们都假设任何商品都可以从任何来源流向任何目的地（考虑同类型商品的需求和供应）。我的问题是独一无二的，它包含固定的源和目标对。是否有针对这种特定情况的算法？
2. 如果我考虑拆分流，即每个流可以采用多条路径，那么解决方案是什么？

我对此感到困惑：

证明网络 G = (V,E) 中的最大流总是可以通过最多 |E| 的序列找到 增加路径。

这是什么原因？

谢谢！

假设有一个具有多条边的网络，对于任意一对顶点 (u, v)，该图包含从 u 到 v 和从 v 到 u 的多条有向边，每条边都有自己的容量和权重。

如何将此多重图简化为一个简单的有向图，在 u 和 v 之间只有一条边？

注意*：不确定这种方法是否正确，我将 u 和 v 之间的各个边的容量和权重相加，并将它们合并为一个从 u 到 v 的超级边，以及一个从 v 到 u 的超级边。但是我如何进一步将这两个合并为 u 和 v 之间的一条边，它应该指向哪个方向？

我无法理解如何在网络中找到具有下限（不是需求）的循环流量。我找到了包含问题描述和解决策略的下一个文档：

1. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
2. http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
3. http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

让我们考虑一个具有以下边的网络（l - 下界，c - 容量）：

1 -> 2 : l = 1 c = 3

2 -> 3 : l = 2 c = 4

3 -> 1 : l = 1 c = 2

据我了解，要解决问题，我们应该采取以下步骤：

1. 把这个问题转化为“有需求的流通问题”。这可以通过下一个公式 dv' = dv - (Lin - Lout) 来完成，其中 'dv' 是原始顶点需求（在我们的例子中它等于零），'Lin' - 顶点输入边的总和下限，并且' Lout' - 顶点输出边下界的总和。
2. 将边容量更新为 c' = c - l
3. 将带有边的源顶点 S 添加到 dv < 0 且容量为“-dv”的每个顶点
4. 添加接收器顶点 T，每个顶点的边 dv > 0，容量为 'dv'
5. 使用任何算法在新网络中找到最大流量，例如 Edmonds-Karp 算法。
6. 如果最大流量的值等于所有与 T 相连的顶点的需求之和，则网络中存在循环。

执行这些步骤后，新网络将是：

S -> 2 : c = 1

2 -> 3 : c = 2

3 -> T：c = 1

1 -> 2 : c = 2

3 -> 1 : c = 1

对顶点的要求：

d1 = 0

d2 = -1

d3 = 1

我们看到最大流量等于 1，并且等于 T 的边的总和，也为 1。它覆盖了边 A->2->3->T。

问题是如何在具有原始边界的原始网络中获得流通流量？

原始网络中存在循环流 - 我们只需将等于 2 的流分配给所有边。

给定一个有向图，我们可以使用 edmonds-karp 或 ford-fulkerson 算法来找到有向图中的最大边不相交路径数。

假设 G 中有 k 条边不相交的路径，如何在多项式时间内找到实际路径？我最好的选择是 BFS，一旦找到路径，将这些边缘标记为已使用。

非常感谢！

我正在尝试使用Ford Fulkerson算法在网络中找到最大流量，它适用于非循环图但是如果有一个循环它会永远循环。这是我用来查找最大流量的代码：

例如，如果我使用上面的程序来解决以下网络：

它将无限期地运行，我如何找到此类网络中的最大流量？

更新：

我忘记在上面的代码中跟踪深度优先搜索 dfs 函数中的访问边，所以我修复了它：

但是它仍然无限循环。

我正在努力为算法课程提出解决此问题的方法：

你去一家商店，想要购买n = {n ₁ , n ₂ , ..., n _n }商品，其中商品可以不同也可以不同。

这家商店有以下促销活动：“如果顾客购买了两件商品，其价格加起来以 11 美分、33 美分或 55 美分结尾，他将收到一张价值相应美分的代金券。”

问题是提出一种算法，该算法计算购买给定商品集合的最佳策略，其中希望总成本最小化。

例如：如果您需要购买价格为（1.01 美元、2.10 美元和 3 美元）的 3 种产品（n ₁、n ₂、n ₃），您应该同时购买 n ₁和 n ₂并分别购买 n ₃，得到 a总成本：(1.01 + 2.10) + 3 - (0.11) = 6$。

没有给出任何提示，但我认为我可以使用一些流网络方法。