网络流基本概念(1)残余网络残余网络其实简单来说就是“剩下的网络”。当我们已经安排了一些流量之后每条边还剩多少容量可以流这就是残余网络。而且残余网络里还有一个很神奇的东西反向边。为什么要加反向边呢因为有时候我们之前流的水可能流错了我们需要一种方法把水“退回来”然后重新流到别的地方。反向边就是用来退水的。还是这个例子假设我们现在已经流了一些水了容量/流量5/53/34/42/23/04/36/63/2STABCD那么它的残余网络大概就是这样的只画了有剩余容量的边和反向边00003101STABCD我们发现原来的边如果还剩容量残余网络里就有这条边容量是剩下的量。如果原来的边流了水残余网络里就会多出一条反向的边容量等于流过的水量。增广路有了残余网络我们就可以找增广路了。增广路就是一条从原点 S 到汇点 T 的路径而且这条路径上的每一条边在残余网络里都有剩余容量也就是容量大于 0。如果我们找到了一条增广路那就说明我们还可以往这条路上再流一些水。能流多少水呢取决于这条路上剩余容量最小的那条边木桶效应。比如我们在残余网络里找到了这样一条路211STAD这条路上的最小容量是 1A 到 D 和 D 到 T 都是 1。那我们就可以让总流量增加 1。然后我们要更新残余网络这条路上的边容量减 1反向边容量加 1。最大流最大流就是原点 S 流出的总流量的最大值也就是汇点 T 流入的总流量的最大值。怎么求最大流呢其实思路很简单只要能在残余网络里找到增广路就沿着这条路流水更新残余网络。直到找不到增广路为止。这时候的流量就是最大流。这个过程有点像挤牙膏一点点把能流的水都挤过去。最小割割是什么呢就是把网络里的某些边切断使得原点 S 和汇点 T 不连通。最小割就是切断的边的容量之和最小。我们可以想象一下如果要阻止水从 S 流到 T我们需要关掉哪些水管。为了让关掉的代价最小我们会找那些容量最小的关键水管。最大流最小割定理这是一个很重要的定理虽然证明很难但是结论很好记一个网络的最大流等于它的最小割。也就是说我们辛辛苦苦算出来的最大流其实也就是把 S 和 T 分开所需的最小代价。这个定理在很多题目里都有用有时候求最大流很难我们可以转化成求最小割或者反过来。总结网络流其实就是一种建模工具。当我们遇到题目里有很多限制条件比如管道容量、流量守恒的时候就可以想想能不能用网络流来做。原点 S 是起点汇点 T 是终点。容量是限制流量是实际流的量。可行流要满足容量限制和流量守恒。残余网络用来找增广路。最大流等于最小割。