最大流边约束

Question

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

Answer 1

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

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

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