最大流邊約束

Question

如何解決最大流問題，其中圖中的某些邊必須具有流= 3n，其中n是非負整數？換句話說，你如何限制某些邊緣必須有可被3整除的流量呢？例如，這些邊可能具有流0,3,6,9 ...但可能不具有流1,2,4,5 ......理想情況下，我想要一種方法來計算像這樣的圖上的最大流量，也是最大流量配置中每個邊緣上的流量。

Answer 1

基本上，實現一個算法尋找最大流量，並建立在你的約束。

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

現在
注意，這個值是基於最小路徑上的每個邊緣。這是您檢查其中一條邊是否有一些約束的位置，然後相應地更改c_f(p)的值。