algorithm - 具有不同约束的网络流

Question

考虑一个简单的网络流模型:G = (V,E)，源节点S，汇节点T。对于每条边E[i]，它的容量是C[i]。

然后边 E[i] 上的流 F[i] 被限制为 C[i] 或 0，即F[i]属于{0, C[i]}。

如何计算从S到T的最大流量？这还是网络流量问题吗？

Answer 1

修改后的流问题的决策变量是 NP 完全的，事实证明 subset sum problem可以简化为:对于给定的项目 w_1，...，w_n 和总和 W，只需创建一个源 S 通过容量为 w_i 的边 S -> i 连接到每个项目 i。然后通过容量为 w_i 的另一条边 i -> t 将每个项目 i 连接到汇 t。添加容量 W 的边 t -> T。如果经过您的修改，图中的 S-T 最大流量为 W，则存在累积权重为 W 的项目子集。

也就是说，可能没有在所有情况下都能有效解决此问题的算法，但对于并非专门设计为困难的实例，您可以尝试 integer linear program制定问题并使用通用 ILP 求解器找到解决方案。

如果您的容量是由输入大小中的值多项式限制的整数，则可能是伪多项式算法。