最大流边约束

Question

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

Answer 1

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

我的意思是，看看Ford-Fulkerson算法。在算法的2.1线（如维基百科中描述的）你能找到一些

现在
注意，这个值是基于最小路径上的每个边缘。这是您检查其中一条边是否有一些约束的位置，然后相应地更改c_f(p)的值。