最小开销流

解决最小开销流问题，我们仅仅需要构造一个流网络图，并且保证满足之前讨论过的那些限制条件：容量限制、流量守恒以及反对称。而且还要保证如下两个条件。

供应满足

对每个源点si∈S，所有边(si,v)∈E的f(si,v)之和（流出si的流）减去所有边(u,si)∈E的f(u,si)之和（流入si的流）必须小于等于sup(si)，也就是说，每个源点供应的商品的上限是sup(si)。

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

需求满足

对于每个汇点tj∈T，所有边(u,tj)∈E的f(u,tj)之和（流入tj的流）减去所有边(tj,v)∈E的f(tj,v)之和（流出tj的流）必须小于等于dem(tj)。也就是说，每个汇点需要的商品上限是dem(tj)。

为了简化算法的实现，我们将会限制流网络只有一个源点和一个汇点。通过向现存的多源多汇点的流网络图添加两个新顶点，这种流网络可以轻易得到。首先，添加一个新的顶点（s0）成为流网络的源点，然后对每个源点si∈S，添加一条容量c(s0,si)=sup(si)以及开销d(s0,si)=0的边（s0,si）。然后，添加一个新的顶点（tj,tgt）成为流网络的汇点，然后对每个源点tj∈T，添加一条容量c(tj,tgt)=dem(tj)以及开销d(t0,tj)=0的边（tj,tgt）。你可以看到，添加这些顶点和边不会增加原始流网络的开销，但是也不会减少最后计算出的流。

供应sup(si)，需求dem(tj)以及容量c(u,v)都大于0。每条边的航运开销d(u,v)可能大于等于0。计算出结果之后，所有的f(u,v)都会大于等于0。

我们现在准备来解决图8-1中剩下的流网络问题。对于每个问题，我们都会描述如何归约成最小开销流问题。