考虑一个简单的网络流模型：G = (V,E)，源节点S，汇节点T对于每个边E[i]，其容量为C[i]。
然后将边上的流限制为F[i]或E[i]，即C[i]属于0。
如何计算从F[i]到{0, C[i]}的最大流量？这还是网络流量问题吗？
最佳答案
修改后的流问题的决策变量是np完全的，事实证明subset sum problem可以简化为np完全：对于给定的项w_1，…，w劬n和和和w，只需创建一个通过容量w劬的边s->i连接到每个项i的源s，然后通过另一个边i->t连接到容量w劬的汇t。添加一个边t容量W的存在。如果图中的S- T最大流是W的，则存在一个具有累积权重W的子集。
也就是说，在任何情况下都可能没有有效解决此问题的算法，但对于不是特别设计为困难的实例，可以尝试问题的integer linear program公式，并使用通用的ilp解算器来找到解决方案。
如果您的容量是由输入大小中的值多项式限定的整数，则可能存在伪多项式算法。