algorithm - 在给定条件下以最低成本确定图中的最小流量

Question

我最近正在准备 acm-icpc 竞赛。在这里我想知道如何找到最小值给定图中每条边的容量 C、成本 V 和下界流 L(L ≤ C)的条件下，成本最低的流。

Answer 1

首先，我不确定“成本最低的流量最少”是什么意思，但我怀疑您只是指“成本最低的流量”。

其次，流量下限意味着找到“合法流量”并非易事，“合法流量”是一种遵守质量守恒的流量，即入站流量之和等于出站流量之和对于除源节点和汇节点之外的所有节点。 (通常流问题有L=0，这意味着零流是合法的。)实际上，存在不存在合法流的L和C的选择。

我认为您可以从每条边上都等于 L 的流开始找到合法流。图中的一些节点将有盈余流量，而一些节点将有赤字流量。您可以通过找到从盈余节点到不足节点的(低于容量的)路径并沿着该路径插入更多流量来增加流量。重复直到所有剩余为零，否则找不到这样的路径(在这种情况下不存在合法流)。

一旦找到可接受的流量，Ford-Fulkerson 或预流推送算法便可以优化您的流量(修改它以降低总成本)。