网络流
-
2023年3月17日发(作者：项目式学习)IOI2004国家集训队作业：研究报告安徽周源
一种简易的方法求解流量有上下界的网络
中网络流问题
安徽周源
研究命题
一般的，定义一个网络是一个加权的有向图G=(V,E,C)，E中的每条弧(u,v)都有一个
容量上界C(u,v)≥0。
如果人为的规定V中的两个点s和t，其中s没有入度而t没有出度；并为E中的每条弧
(u,v)赋予一个值f(u,v)≥0，f满足以下两个条件：
①除s,t之外的任意一个点i都满足：
EviEiu
vifiuf
),(),(
),(),(；
②任意一条E中的弧(u,v)，都满足f(u,v)≤C(u,v)。
则称f是G的一个可行流，称s为流的源且t是流的汇。前一个条件被称为流量平衡条
件，而后者则是容量限制条件。
而如果一个可行流f使原点提供的流量
Eis
isf
),(
),(达到最大，则称f是G网络的最大流。
如果为G中的每条边再加入一个容量下界：令G=(V,E,B,C)，B(u,v)表示弧(u,v)的容
量下界。这样G就是一个容量有上下界的流网络。类似的定义G中的可行流f：
①除s,t之外的任意一个点i都满足：
EviEiu
vifiuf
),(),(
),(),(；
②任意一条E中的弧(u,v)，都满足B(u,v)≤f(u,v)≤C(u,v)。
同时可以定义G中的最大流f
max
，对容量有上下界的网络来说，还可以定义这个网络的
最小流f
min
：使原点提供流量
Eis
isf
),(
min
),(达到最小的流。
在这篇文章中，我们的讨论就将围绕容量有上下界的网络展开，经过一些必要的讨论，
最后将得到用于解决这一系列问题的一个较为简单的，有着较好的应用价值的算法。
正文
第一部分
为了最终能够解决问题，不妨来看一个简化版的问题：
[问题1.1]在一个有上下界的流网络G中，不设源和汇，但要求任意一个点i都满足流量
IOI2004国家集训队作业：研究报告安徽周源
平衡条件：
EviEiu
vifiuf
),(),(
),(),(
且每条边(u,v)都满足容量限制B(u,v)≤f(u,v)≤C(u,v)的条件下，寻找一个可行流f，或
指出这样的可行流不存在。
不妨称这个问题为无源汇的可行流。
[问题1.1的解答]仔细分析一下，由于普通最大流中对每条边中流量的约束条件仅仅是
f(u,v)≥0，而在这个问题中，流量却必须大于等于某一个下界。因此可以想到，设
f(u,v)=B(u,v)+g(u,v)(*)
其中g(u,v)≥0，这样就可以保证f(u,v)≥B(u,v)；同时为了满足上界限制，有
g(u,v)≤C(u,v)-B(u,v)
令C’(u,v)=C(u,v)-B(u,v)，则大致可以将g(u,v)看作无下界流网络C’中的一个可行流。
当然这样直接转化显然是不对的，因为这样仍无法体现“下界”这个条件。将(*)式代入流
量平衡条件中，对于任意一个点，有：
EviEiu
vigviBiugiuB
),(),(
)],(),([)],(),([
EviEiuEiuEvi
viBiuBiugvig
),(),(),(),(
),(),(),(),(
如果设：
EviEiu
viBiuBiM
),(),(
),(),()(
即M(i)为流入结点i的下界总和减去流出i的下界总和。
如果M(i)非负，那么有：
)(]),([),(
),(),(
iMiugvig
EiuEvi
(1)
设一附加源S
0
，则可以令
C’(S
0
,i)=M(i)。
如果M(i)是负数，那么有：
EiuEvi
iugiMvig
),(),(
),()(]),([(2)
设一附加汇T
0
，令
C’(i,T
0
)=-M(i)。
这里-M(i)是正数。
至此，附加图构造完毕。
在这样一个加入附加源和附加汇的流网络C’中，如果任意g(S
0
,i)或g(i,T
0
)都达到满载，
那么C’中的这一个可行流g一定对应原网络G中的一个可行流f；反之G中的任意一个可
行流f都可以对应C’中的一个g(S
0
,i)或g(i,T
0
)都满载的流。
而让从附加源点流出的弧都满载的可行流，一定是一个从附加源到附加汇的最大流。因
此，求原网络G中的一个可行流等价于求C’中S
0
至T
0
的最大流，并判断从源点流出的弧是
否满载：如果满载，则[问题1.1]有解，否则一定无解。
IOI2004国家集训队作业：研究报告安徽周源
第二部分
[问题1.2]在一个容量有上下界的流网络G中，求源点s到汇点t的一个可行的最大流。
[问题1.2的解答]如果从s到t有一个流量为a的可行流f，那么从t到s连一条弧(t,s)，
其流量下界B(t,s)=a，则这个图一定有一个无源汇的可行流：除了弧(t,s)的容量为a外，
其余边的容量与f相同。
如果从s到t的最大流量为a
max
，那么从t到s连一条下界B(t,s)=a’>a
max
的弧(t,s)，
则从在这个改造后的图中一定没有无源汇的可行流：否则将这个可行流中的弧(t,s)除去，就
得到了原图中s到t的流量为a’的流，大于最大流量a
max
，产生矛盾。
如果给定一个参数a，如何判断在G中从s到t是否有一个流量为a的可行流呢？综上
所述，判断在G中是否有a的可行流和判断在改造后的图中是否有一个无源汇的可行流完
全等价。因此，执行一次普通最大流算法，就可以完成这个任务了。
下面回到[问题1.2]中来，我们不妨二分枚举这个参数a，每次改造图后执行一次最大流
来判断是否有s到t的流量为a的可行流。这样找到a能取到的最大值，也就是G图中的最
大流a
max
了。
在一般问题中，如果所有弧上的容量为整数，那么算法一定可以在有限次计算之后停止，
而算法的时间复杂度约为[log
2
流量]次的最大流过程，采用朴素的预流推进算法，执行一次
最大流算法约需要O(N3)的时间，而[log
2
流量]基本可以看作与[log
2
N]看作同阶。因此这个算
法的时间复杂度约为O(N3log
2
N)。
在实际应用中，这个算法是非常有价值的。但从纯理论上说，这并不是一个多项式算法，
特别是当流量可能为小数的时候，算法可能会无止境的执行下去。一种解决方法是规定一个
较小的误差范围，这样算法的时间复杂度为O(N3*[log
2
精度])：从理论上说，这也只能算一
个近似算法。另一种解决方法则是直接将答案离散为整点再进行二分，这样最多有O(2N)
个整点，因此算法的时间复杂度为O(N4)。当然这种方法效率不算很高，而且实现起来很麻
烦，在实际竞赛中也并不需要仅仅为追求理论上的“快感”而做出这么大的牺牲。
[问题1.3]在一个容量有上下界的流网络G中，求源点s到汇点t的一个可行的最小流。
[问题1.3的解答]与[问题1.2]类似，只是在加入弧(t,s)后二分(t,s)的容量上界C(t,s)即可。
此类问题还有一些简易的扩展，如求容量有上下界的流网络G中的最小费用最大流之
类，其本质思想都是“二分参变量”，这里不再赘述。
附录
SGU中两道流量有下界试题：
p194ReactorCooling和p176FlowConstruction；