algorithm - 最大流量边缘约束

Question

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

Answer 1

基本上，实现一个算法来寻找最大流量，并建立你的约束。

我的意思是，看看Ford-Fulkerson算法。
请注意，在算法的第 2.1 行（如 Wikipedia 中所述）中，您会发现一些

现在，该值基于路径上每条边的最小值。您可以在此处检查这些边之一是否有一些约束，然后c_f(p)相应地更改 的值。