上下界网络流
上下界网络流
主要有无源汇上下界可行流，有源汇上下界可行流，有源汇上下界最大流，有源汇上下界最小流，上下界最小费用可行流等。
无源汇上下界可行流
即求出类似于下图的流量网络的可行流：
首先，我们将这个网络拆成两个结构与该网络相同的普通网络，一个每条边的容量为原网络对应边的流量下界，另一个为对应边的流量上界与下界之差。
为了使每条边都满足流量下界，我们强制使下界网络全部满流。
但是下界网络满流后不一定流量平衡，所以我们要对差网络进行一定的修改以弥补这种不平衡。
我们分别考虑下界网络中的点。
\(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\)。最后的费用是下界网络满流的费用，加上在差网络上跑最小费用最大流后得到的费用之和。而前者即所有边的容量与费用乘积的和。注意，这样求出来的是满足最小费用的可行流，而不是满足流最大的前提下费用最小的流。