上下界网络流

主要有无源汇上下界可行流，有源汇上下界可行流，有源汇上下界最大流，有源汇上下界最小流，上下界最小费用可行流等。

即求出类似于下图的流量网络的可行流：

首先，我们将这个网络拆成两个结构与该网络相同的普通网络，一个每条边的容量为原网络对应边的流量下界，另一个为对应边的流量上界与下界之差。

为了使每条边都满足流量下界，我们强制使下界网络全部满流。

但是下界网络满流后不一定流量平衡，所以我们要对差网络进行一定的修改以弥补这种不平衡。

我们分别考虑下界网络中的点。

1 号点：流入 3，流出3，平衡。

2号点：流入3，流出1，不平衡，流入比流出多2，所以我们希望在差网络中，2的流出应该比流入多2，于是我们在差网络中新设一个源点，然后加入一条容量为2的附加边从源点连向2，这样在差网络平衡时，除去附加边，2点的流出恰好比流入多2。

3号点：流入2，流出1，不平衡，同2处理。

4号点：流入3，流出5，不平衡，流出比流入多2，所以我们希望在差网络中，4的流入应该比流出多2，于是我们在差网络中新设一个汇点，然后加入一条容量为2的附加边从4连向汇点，这样在差网络平衡时，除去附加边，4点的流入恰好比流出多2。

5号点：流入1，流出2，不平衡，同4处理。

也就是说，如果下界网络中某个点有\(x\)的净流入，在差网络中我们就从源点向它连一条容量为\(x\)的附加边；相反，如果下界网络中某个点有\(x\)的净流出，在差网络中我们就从它向汇点连一条容量为\(x\)的附加边。这样，我们把差网络修改如下：

在差网络上跑一遍最大流，把每条非附加边的流，加上下界网络的满流，就是一个可行流。但是，如果跑完最大流发现，存在附加边未满流，那说明平衡条件没有得到满足，于是原图不存在可行流。

在实际中，是不需要建立下界网络的，只需要对差网络进行操作即可。另外最后判断的时候并无必要遍历所有附加边，而只需要判断所有从源点出发的边，或者判断所有连向汇点的边即可，因为根据网络流的性质，两者容量和应该相等，于是它们要么都满流，要么都不满流。

如果原网络中存在源点和汇点呢？

很简单，我们只需要加一条从汇点到源点，下界为 0，上界为\(+\infty\)的附加边就行了。就得到一张和原图等价的无源汇流量网络，于是转化成了无源汇上下界可行流问题。此时从源点到汇点的可行流流量，即为从汇点到源点的那条附加边的流量（注意下界网络中对应边流量为0）。

注意，这时原图中的源点和汇点需要当作一般点处理，还是要新建源点和汇点。

按照上一节的方法，我们已经得到了一个可行流，且知道它的流量就是T到S的附加边的流量。

要求从S到T的最大流，我们可以在差网络中把所有附加边删除，然后以S与T为源点与汇点，再求残余网络的最大流，加上可行流的流量即为原网络的最大流。这是因为，可行流已经保证了流量平衡，那么删去附加边后，我们再跑一次最大流把残余网络“榨干”，最后得到的流仍保证是平衡的。

当然实际上S与T连接的附加边不需要删，这种出度或入度为0、又非源汇点的点是不影响最大流的，何况如果存在可行流，它们的残余容量已经为0了。

跟上面几乎完全相同，只需要在拆掉附加边后，从汇点到源点，而不是从源点到汇点跑一遍最大流。可行流的流量，减去从汇点到源点的最大流即为答案。如果说上下界最大流是把残量网络“榨干”，那么上下界最小流就是把不需要的流“退回”。

和（无/有源汇）有上下界可行流的原理相同，也是拆成两个网络。所有附加边的费用设为0。最后的费用是下界网络满流的费用，加上在差网络上跑最小费用最大流后得到的费用之和。而前者即所有边的容量与费用乘积的和。注意，这样求出来的是满足最小费用的可行流，而不是满足流最大的前提下费用最小的流。