预计阅读本页时间：-
第8章 网络流算法
概述
有很多问题可以抽象成顶点和有容量限制的边的网络。如何解决这类问题将是本章所要关注的。Ahuja（1993）对现有大量的网络流算法应用进行了深入的讨论。
任务分配
现在雇员们要完成一些任务，由于不同雇员在相同个任务上的花费不同，所以我们需要找到一种分配方式，使得总花费最小。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
二部图匹配
有一些求职者需要面试一些工作，寻找到一个合理的分配方式，使得尽可能多的人能够找到能够胜任的工作。
运输问题
找到从工厂运输商品到零售商店性价比最高的方法。
转运问题
找到从工厂运输商品到零售商店性价比最高的方法，但是这类问题中，我们可以使用一些中转站作为临时仓库。
最大流
给定一个网络，网络中的每条边都有一个最大容量，计算出这个网络能够支持的最大流。
首先我们会阐述网络流问题之间的关系，这样能够帮助我们理解这些问题是如何解决的。图8-1描绘的是这些问题的关系。一条有向边将问题的一般化实例和问题的特例联系起来。例如运输问题就是转运问题的一个特例，因为运输图并不包含任何的中转节点。因此一个能够解决转运问题的程序肯定能够用于解决运输问题。
在本章中，我们将阐述Ford-Fulkerson算法。此算法用来解最大流问题。Ford-Fulkerson算法也可以直接用于二部图匹配问题，它们之间的关系如图8-1所示。而且，一旦理解了Ford-Fulkerson算法的基本原理，我们不难发现，Ford-Fulkerson算法的框架可以用来解决最小耗费流问题，例如转运问题、运输问题以及任务分配问题。
从理论上来说，你可以利用线性编程（LP）来解决图8-1的所有问题，但是你必须得先将这些问题转换成正确的线性表示形式，而且得到的解能够转换成原有的形式。在本章末尾，我们将会举例使用线性编程来解网络流问题。实际上，本章描述的特定算法解决图8-1的问题效率要比LP高数个数量级。
网络流
如图8-2所示，通常我们抽象出来的网络流模型是一个有向图G=(V,E)，V是顶点集，E是边集。图是连通的（虽然并不是每条边都需要展示出来）。有一个源点s∈V，s生产商品，然后通过图的边运输到汇点t∈V消费（也称为终点或者目标点）。网络流假设能够生产无限多的商品，并且汇点能够消费完所有接收到的商品。
每条边（u,v）都有一个流f(u,v)，表示从u运输到v的商品单位数目。同样每条边有一个容量c(u,v)，表示从u运输到v的最大商品单位数。在图8-2中，每个顶点和每条边都做了标记，我们用数字标记顶点（源点和汇点用s和t标记），用f/c标记边，f/c表示一条边上的流容量以及最大的流容量。例如边（s,v1）标记为5/10，表示这条边上有5个单位的商品在通过这条边，这条边能够承受的最大容量为10个单位。当没有单位通过边（例如v5和v2的边），那么只会在一个灰色方格中标示容量。
在一个流通过网络时，必须满足如下的限制条件。
容量限制
通过一条边的流f(u,v)不能为负，而且不能超过边的容量c(u,v)，即0≤f(u,v)≤c(u,v)。如果在网络中不存在边（u,v），那么c(u,v)=0。
流守恒
除开源点s和汇点t，每个顶点u∈V必须满足所有的入流等于所有的出流。这个性质确保了在网络中，除了源点和汇点，不会产生和消耗流。
反对称
从一致性角度来看，f(v,u)表示的是从顶点u到v的网络流。f(u,v)=-f(v,u)，即使在一个有向图中存在两条边（u,v）和（v,u），这个性质也同样成立。
在接下来的算法中，我们使用一条网络路径＜v1,v2,……,vn＞，表示n-1条连续的边（vi,vj），这条网络路径中不存在环。在图8-2的有向图中，一条可能的网络路径是＜v3，v5,v2,v4＞。在一条网络路径中，我们忽略边的方向。图8-3的一条可能的网络路径是＜s,v1,v4,v2,v3,t＞。
