一些英文的缩写

普通人可能很难想象中国的 汽车 规模究竟有多庞大！

据公安部交通管理局2021年1月发布的消息，2020年全国机动车保有量达 372亿辆 ，其中 汽车 281亿辆 。

目前，全国有70个城市的 汽车 保有量超过100万辆，31个城市超200万辆，13个城市超300万辆。

其中，苏州、上海、郑州超过400万辆，而北京、成都、重庆三城的 汽车 保有量更是超过500万辆，数量之多，令人咋舌。

与快速增长的私家车形成对比的是，我国中大型城市的车位配比低得可怜，平均只有1:05- 1:08，低于国际的1:13。

根据《人民日报》报道，截止到2020年末，我国全国车位缺口已达约 8,000万 个，供给率仅在 40% 左右。

以深圳市为例，目前深圳机动车保有量为352万辆，而深圳整体经营性停车场加路边泊车位和非经营性泊车位，总量大约为250万，缺口大约还需100万。

而上海停车位缺口均在200万个以上，北京的停车缺口甚至高达400万个。

如何解决这种“车多位少”的窘境，可能的 科技 解决方案还是要从 “立体车库” 和 “智慧停车” 两个方面着手。

毋庸置疑，机器人技术在现代生活中发挥着越来越突出的作用。

似乎每天都有越来越多的日常生活变得更加自动化，其中机器人技术改造后的立体车库就是代表。

立体车库（Stereo Garage）是用来最大量存取储放车辆的机械或机械设备系统。

最早的立体车库是1905年在法国巴黎庞蒂厄街的车库，该车库由一个多层混凝土结构组成，内部有电梯将 汽车 运送到上层，服务员将 汽车 停放在那里。

1951年，第一座无人驾驶停车库也在美国华盛顿特区开业。

我国也于90年代初开始研究开发机械立体停车设备，距今已有近三十年的历程。

到了1994年，进一步升级的“机器人停车”（robotic parking）概念出现，第一个自动化车库于2002年启用。

与传统停车场相比，立体车库所提供的空间节省主要在于大幅减少与 汽车 停放没有直接关系的空间。

例如，因为不需要为 汽车 驶入停车位或打开车门(司机和乘客)留出空间，所以停车位的宽度和深度(以及停车位之间的距离)大大减少；

不需要开车道或坡道，就可以把车开到/从入口/出口到停车位；

由于停车场内没有行人（司机和乘客），所以天花板的高度降到最低，也不需要走道、楼梯或电梯。

另外，由于取消了坡道、行车道并降低了天花板高度，立体车库所需的结构材料比多层停车库少得多。许多立体车库采用钢结构框架（有些采用薄混凝土板），而不是多层停车库的整体混凝土设计。

除了节省空间外，许多立体车库还有一些额外的好处。

如：由于停放的车辆没有公共通道，因此停放的车辆及其物品更加安全；

消除停车场的轻微损坏，如擦伤和凹陷；

司机和乘客不用走过停车场或车库，更安全；

驾车四处寻找停车位的情况不再出现，从而减少了尾气排放；

只需要最低限度的通风和照明；

残疾人通道得到改善；

将停车结构的体量和视觉影响降到最低；

缩短施工时间，等等。

也正因此，中国重型机械工业协会停车设备工作委员会的数据显示，2019年国内新增机械式立体车库项目2,552个，新增机械式停车泊位8935万个。

一线城市中，上海、北京、广州当年新增立体车库泊位分别达到55,753个、29,815个和26,629个。

以北京大兴国际机场为例，该机场设置停车楼1处，共4,200个车位，停车场5处共4,800个车位，其中就首度加入了机器人泊车系统。

2019年，我国机械式停车设备销售规模为1635亿元。

诸如打造国内首个停车机器人项目的 怡丰机器人 在2019年的停车机器人销售额就近亿元。

而在全球范围内，这种机器人立体车库还催生了Worldwide Robotic Automated Parking、Westfalia、LT Smart、Automotion Parking Systems、Park Plus等知名公司。

塑造机器人立体车库的另一个趋势是智慧城市的崛起。

随着物联网技术越来越先进，价格越来越便宜，互联城市的想法变得越来越接近现实。

这些系统的特点是连接的基础设施越多，性能就越好，而机器人车库的连接性已经比较成熟，智慧停车业务大范围铺开的时机已经到来。

智慧停车指的就是将无线通信技术、移动终端技术、GPS定位技术、GIS技术等综合应用于城市停车位的采集、管理、查询、预订与导航服务。

这一举措不仅可以实现停车位资源的实时更新、查询、预订与导航服务一体化，还能够实现停车位资源利用率的最大化、停车场利润的最大化和车主停车服务的最优化。

如果说机器人立体车库是在“硬件”上变革传统停车场，那么智慧停车就是塑造了停车场的“大脑”，二者结合就是下一代停车场的基本形态。

从规模上，智慧停车可以分为城市级、场库级和车位级。

城市级： 停车设备数据通过物联网方式上传到城市平台，政府的城市级云平台与停车企业的云平台进行线上对接，获得停车场地数据。

其中运用到的技术包括NB-IoT（窄带物联网）技术和LoRa（远距离无线电）技术。

NB-IoT技术利用窄带通信的功耗低、覆盖广、密度高优势，使停车设备直接联网，地磁、地锁、充电桩、道闸可以把信息源源不断传输到网络平台。LoRa技术则在近年形成了行业规范和共同平台，可以使小区联网组成大网络。

场库级： 场库级应用场景包括停车场、停车库、路侧停车等，最主要技术是车牌识别技术和不停车电子收费(ETC)技术。

车位级： 停车位级别有三种技术，视频桩技术、地磁技术和智能车位锁技术。

2018年4月21日，上交会（第六届中国（上海）国际技术进出口交易会）期间揭牌成立了“上海城市智慧停车产业联盟”。

今年2月9日，交通运输部办公厅发布《关于开展ETC智慧停车城市建设试点工作的通知》，选定北京等27个城市作为试点城市、江苏作为省级示范区，先期开展ETC智慧停车试点工作。

此前，国家发展改革委、交通运输部曾发布《加快推进高速公路电子不停车快捷收费应用服务实施方案》，鼓励ETC在停车场等涉车领域应用。

目前，一些地方城市已经开始ETC智慧停车领域进行了尝试。

佛山部分加油站通过铺设ETC无感支付车道，精准识别车辆进站顺序及停位置，加油后ETC无感支付自动扣款，使支付过程瞬间完成。

在中山，该市则已经改造了13,000多个智慧停车泊位，路侧停车场的停车配套设施改造接入智慧管理系统，并与公安机关交通管理部门、城管部门的平台联通。

前瞻产业研究院初步预计，国内智慧停车市场规模在未来5年将保持20%以上的复合平均增长率，到2025年行业产值有望接近400亿元人民币。

除了机器人立体车库和智慧停车这两个百亿级别的市场值得期待外，其实，围绕“停车”概念还有两个规模上万亿的蓝海值得开拓。

近年来，各地方政府在停车场建设模式上不断创新，由政府主导逐渐转向PPP模式，引入民间资本共同打造停车场建设。

例如，位于宣武门外大街的停车场是北京市首个全智能化的停车场。

该停车场为企业与广渠门内街道办事处合作的BOT项目，前者出钱并享受停车场20年的经营权，后者出地并允许企业收取周围的路边停车位的20年的停车费。

而在盘活停车场的道路上，四川走得更远。

去年3月，川投集团控股子公司川投航信主导实施的邛崃市公共停车场PPP项目一期成功落地。

项目总投资849亿元，首期盘活邛崃市政府存量停车场资产52亿元，以邛崃市主要城镇的19,666个公共停车位12年的经营权及收益权进行转让，并以TOT（转让-经营-移交）模式进行运作，转让资金可用于支持地方经济发展建设。

而邛崃市只是隶属于成都的一个县级市，以全国近3,000个县区级行政单位计算，整体公共停车位转让收益有达到 15万亿元 上下。

除了公共停车场，商品住宅的配套停车场也是一个不容忽视的庞大市场。

随着电动 汽车 的加速普及，充电桩成为私家车的必备品，这也就相应地促使过去乱停乱放向规范化停车转变。

根据世联评估价值研究院数据，2020年全国新建商品住宅销售面积154,878万平方米，按车位比1:1计算，新增车位也在千万级别，对应市场规模也有 万亿元 。

有鉴于此，从机器人立体车库和智慧停车的百亿市场到公共停车场转让和商品房配套停车场的万亿元想象力，“停车”从来不是一个应该被忽视的小生意。

一．Ford和Fulkerson迭加算法
基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流
迭加算法：
1) 给定目标流量F或∞,给定最小费用的初始可行流=0
2) 若V(f)=F,停止,f为最小费用流;否则转(3)
3) 构造 相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止f就是最小费用最大流
具体解题步骤：
设图中双线所示路径为最短路径，费用有向图为W（fij）．
在图(a)中给出零流 f,在图(b)中找到最小费用有向路,修改图(a)中的可行流,δ=min{4,3,5}=3,得图(c),再做出(c)的调整容量图,再构造相应的新的最小费用有向路得图(d), 修改图(c)中的可行流, δ=min{1,1,2,2}=1,得图(e),以此类推,一直得到图(h),在图(h)中以无最小费用有向路,停止,经计算:
图(h)中 最小费用=14+33+24+41+11+42+11+31=38
图(g)中 最大流=5
最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题 ，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。
二．圈算法：
1) 利用Ford和Fulkson标号算法找出流量为F(<=最大流)的流f
2) 构造f对应的调整容量的流网络N'(f)
3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转(4)
4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3)
三，ZKW费用流
费用流是网络流的一个很重要的组成部分，也是非常有用的一种图论模型，关于费用流的算法，流传比较广的主要是消圈和增广路算法，而近来炒得沸沸扬扬的ZKW算法也是一种非常优秀的算法，这里我就谈谈我对此算法的一些理解。
此算法是由ZKW大牛创立，主要思想仍然是找增广路，只是有了一些优化在里边。原来我们找增广路主要是依靠最短路算法，如SPFA。因此此算法的时间复杂度主要就取决于增广的次数和每次增广的耗费。由于每一次找增广路是都是重新算一遍，这样似乎显得有些浪费，如果我们能够缩短找增广路的时间，那必定会大大地优化算法。
值得注意的是，在寻求最短路得过程中，设dis[i]为i到起点的距离，对于每一条由i引向j的边，必有dis[j]<=dis[i]+map[i][j]；既然满足这样的恒等式，我们就可以借用KM算法的调整思想来寻求最短路，每次只走dis[j]=dis[i]+map[i][j]的路径，一旦不存在到达终点的路径，就扫描每一条边，找到最小的距离增加值，使得有至少一条新边被加入相等子图。
算法流程如下：
1将dis数组清零，表示当前的相等子图内只有起点。
（如果存在负权边，必须要用spfa跑一遍，初始化出dis数组，下面的第二题就是这样的例子）。
2深搜，如果到达终点，全部回退更改流量，再进行步骤2；否则，转3。
3修改dis的值，如果无法修改，结束程序，已经找到的答案，反之转2。
有上下界
v上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧<Vi, Vj>加上一个下界限制Aij (即必须满足Aij≤fij)。
v弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了。
网络算法
一、网络流的基本概念
先来看一个实例。
现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下图：
每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？
这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件：
1、 有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
2、 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
3、 每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
则称之为网络流图，记为G = (V, E, C)
譬如图5-1就是一个网络流图。
1．可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
(1) 每一条弧(i,j)有fij≤cij。
(2) 除源点S和汇点T以外的所有的点vi，恒有：
该等式说明中间点vi的流量守恒，输入与输出量相等。
(3) 对于源点S和汇点T有：
这里V(f)表示该可行流f的流量。
例如对图5-1而言，它的一个可行流如下：
流量V(f) = 5。
2．可改进路
给定一个可行流f=。若fij = cij，称<vi, vj>为饱和弧；否则称<vi, vj>为非饱和弧。若fij = 0，称<vi, vj>为零流弧；否则称<vi, vj>为非零流弧。
定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。
譬如在图5-1中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
给定一个可行流f，P是从S到T的一条道路，如果满足：
那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。具体方法下一节会重点介绍，此不赘述。
3．割切
要解决网络最大流问题，必须先学习割切的概念和有关知识。
G = (V, E, C)是已知的网络流图，设U是V的一个子集，W = V\U，满足S U，T W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：
例如图5-1中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
定理：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) ≤ C(U, W)。
通俗简明的讲：“最大流小于等于任意割”。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。
下面我们给出证明。
网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。
二、求最大流
何谓最大流？首先它必须是一个可行流；其次，它的流量必须达到最大。这样的流就称为最大流。譬如对图5-1而言，它的最大流如下：
下面探讨如何求得最大流。
在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。
对可改进路P上的弧<vi, vj>，分为两种情况讨论：
第一种情况：<vi, vj>∈P+，可以令fij增加一个常数delta。必须满足fij + delta ≤ cij，即delta ≤ cij – fij。
第二种情况：<vi, vj>∈P-，可以令fij减少一个常数delta。必须满足fij - delta ≥ 0，即delta ≤ fij
根据以上分析可以得出delta的计算公式：
因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta > 0。
容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta > 0）。
因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？
答案是肯定的。下面我们给出证明。
定理1 可行流f是最大流的充分必要条件是：f中不存在可改进路。
证明：
首先证明必要性：已知最大流f，求证f中不存在可改进路。
若最大流f中存在可改进路P，那么可以根据一定规则（详见上文）修改P中弧的流量。可以将f的流量放大，这与f是最大流矛盾。故必要性得证。
再证明充分性：已知流f，并且f中不存在可改进路，求证f是最大流。
我们定义顶点集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，则y∈U;
若x∈U，且fyx>0，则y∈U。
（这实际上就是可改进路的构造规则）
（c） W = V \ U。
由于f中不存在可改进路，所以T∈W；又S∈U，所以U、W是一个割切（U, W）。
按照U的定义，若x∈U，y∈W，则fxy = cxy。若x∈W，y∈U，则fxy = 0。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得证。
根据充分性证明中的有关结论，我们可以得到另外一条重要定理：
最大流最小割定理：最大流等于最小割，即max V(f) = min C(U, W)。
至此，我们可以轻松设计出求最大流的算法：
step 1 令所有弧的流量为0，从而构造一个流量为0的可行流f（称作零流）。
step 2 若f中找不到可改进路则转step 5；否则找到任意一条可改进路P。
step 3 根据P求delta。
step 4 以delta为改进量，更新可行流f。转step 2。
step 5 算法结束。此时的f即为最大流。
三、最小费用最大流
1．问题的模型
流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。
图5-8是一个最简单的例子：弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为34=12。
容易看出，此图的最大流（流量是8）为：fs1 = f1t = 5, fs2 = f2t = 3。所以它的费用是：35+45+73+23 = 62。
一般的，设有带费用的网络流图G = (V, E, C, W)，每条弧<Vi, Vj>对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：
(a) 流量V(f)最大。
(b) 满足a的前提下，流的费用Cost(f) = 最小。
就称f是网络流图G的最小费用最大流。
2．算法设计
我们模仿求最大流的算法，找可改进路来求最小费用最大流。
设P是流f的可改进路，定义 为P的费用（为什么如此定义？）。如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。
求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。
算法可描述为：
step 1 令f为零流。
step 2 若无可改进路，转step 5；否则找到最小费用可改进路，设为P。
step 3 根据P求delta（改进量）。
step 4 放大f。转step 2。
step 5 算法结束。此时的f即最小费用最大流。
至于算法的正确性，可以从理论上证明。读者可自己思考或查阅有关运筹学资料。
2．最小费用可改进路的求解
求“最小费用可改进路”是求最小费用最大流算法的关键之所在，下面我们探讨求解的方法。
设带费用的网络流图G = (V, E, C, W)，它的一个可行流是f。我们构造带权有向图B = (V’, E’)，其中：
1、 V’ = V。
2、 若<Vi, Vj>∈E，fij<Cij，那么<Vi, Vj>∈E’，权为Wij。
若<Vi, Vj>∈E，fij>0，那么<Vj, Vi>∈E’，权为-Wij。
显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。
故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。
现在的问题变成：给定带权有向图B = (V’, E’)，求从S到T的一条最短路径。
考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法。
设Short[k]表示从S到k顶点的最短路径长度；从S到顶点k的最短路径中，顶点k的前趋记为Last[k]。那么迭代算法描述如下：（为了便于描述，令n = |V’|，S的编号为0，T的编号为n+1）
step 1 令Short[k]  +∞（1≤k≤n+1），Short[0]  0。
step 2 遍历每一条弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，则令Short[j]  Short[k] + <k, j>，同时Last[j]  k。倘不存在任何一条弧满足此条件则转step 4。
step 3 转step 2
step 4 算法结束。若Short[n + 1]= +∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。
一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。
3．思维发散与探索
1）可改进路费用：“递增！递增？”
设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？
2）迭代法：“小心死循环！嘿嘿……”
迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？
3）费用：“你在乎我是负数吗？”
网络流图中的费用可以小于零吗？
4）容量：“我管的可不仅是弧。”
网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。你能解决吗？
4．C++代码实现 #include<cstdio>#include<cstring>#include<algorithm>#include<queue>usingnamespacestd;intH[105],X[40005],P[40005],from[40005],flow[40005],cost[40005],tot;inlinevoidadd(intx,inty,intz,intk){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;from[tot]=x;cost[tot]=k;}intf,c;intn,m;intS,T;intd[105],a[105],p[105];structN{intx,w;friendbooloperator<(Na,Nb){returnaw>bw;}N(inta=0,intb=0){x=a,w=b;}};priority_queue<N>q;boolspfa(){memset(d,0x3f,sizeof(d));d[S]=0;a[S]=inf;p[S]=0;intx;qpush(N(S,0));while(!qempty()){x=qtop()x;qpop();if(x==T)continue;for(inti=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]>d[x]+cost[i]){d[P[i]]=d[x]+cost[i];a[P[i]]=min(a[x],flow[i]);p[P[i]]=i;qpush(N(P[i],d[P[i]]));}}while(!qempty()&&d[qtop()x]!=qtop()w)qpop();}if(d[T]==inf)return0;f+=a[T];c+=a[T]d[T];x=T;while(x!=S){flow[p[x]]-=a[T];flow[p[x]^1]+=a[T];x=from[p[x]];}return1;}intmain(){#ifdefLOCALfreopen(intxt,r,stdin);freopen(outtxt,w,stdout);#endifInput();while(spfa());maxflow=f,mincost=c;return0;}四、有上下界的最大流
上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧<Vi, Vj>加上一个下界限制Aij（即必须满足Aij≤fij）。
例如图5-9：
弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10(b)。
那么有上下界的网络最大流怎么求呢？
一种自然的想法是去掉下界，将其转化为只含上界的网络流图。这种美好的愿望是可以实现的。具体方法如下：
设原网络流图为G = (V, E, C, A)，构造不含下界的网络流图G’ = (V’, E’, C’)：
1、 V’ = V∪{S’, T’}
2、 对每个顶点x，令 ，若h-(x)≠0，就添加一条弧<S’, x>，其上界为h-(x)。
3、 对每个顶点x，令 ，若h+(x)≠0，就添加一条弧<x, T’>，其上界为h+(x)。
4、 对于任何<Vi, Vj>∈E，都有<Vi, Vj>∈E’，其上界C’ij = Cij – Aij。
5、 新增<T, S>∈E’，其上界CTS = +∞。
在G’中以S’为源点、T’为汇点求得最大流f’。若f’中从S’发出的任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得原图的一个可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正确性很容易证明，留给读者完成）
然后再求可改进路（反向弧<Vi, Vj>必须满足fij≥Aij，而非fij≥0），不断放大f，直到求出最大流。
我们看到，上几节所讨论的一种可行网络流实际上是{Aij = 0}的一种特殊网络流，这里提出的模型更一般化了。解决一般化的复杂问题，我们采取的思路是将其转化为特殊的简单问题，加以研究、推广，进而解决。这是一种重要的基本思想：化归——简单有效。基于这种思想，请读者自行思考解决：
1、 有上下界的最小流。
2、 有上下界的最小费用最大流。
五、多源点、多汇点的最大流
已知网络流图有n个源点S1、S2、……、Sn，m个汇点T1、T2、……、Tm，，求该图的最大流。这样的问题称为多源点、多汇点最大流。
它的解决很简单：
1、 增设一个“超级源”S’，对每个源点Si，新增弧<S’, Si>，容量为无穷大。
2、 增设一个“超级汇”T’，对每个汇点Ti，新增弧<Ti, T’>，容量为无穷大。
3、 以S’为源点、T’为汇点求最大流f。
4、 将f中的S’和T’去掉，即为原图的最大流。
算法正确性显然。
六、顶点有容量限制的最大流
上一节已经提出了这个问题，即对于进出每个顶点的流量也规定一个上限，这样的最大流如何求？
既然我们已经解决了“边限制”问题，现在何不把“点限制”问题转化为“边限制”呢？具体办法如下：
1、 对除源点和汇点之外的每个顶点i拆分成两个顶点i’和i’’。新增一条弧<i’, i’’>，其容量为点i的流量限制。
2、 对于原图中的弧<i, j>，我们将其变换成<i’’, j’>。
3、 对变换后的图求最大流即可。
这里我们又一次运用到了化归的思想：将未知的“点限制”问题转化为已知的“边限制”问题。
七、网络流与二部图的匹配
{二部图和匹配的定义可参见本书专门介绍二部图匹配的章节}
设二部图为G = (X, Y, E)。
增设点S’，对于所有i∈X，新增弧<S’, Xi>，容量为1；增设点T’，对于所有i∈Y，新增一条弧<Yi, T’>，容量也为1。原图中所有的弧予以保留，容量均为+∞。对新构造出来的网络流图以S’为源点、T’为汇点求最大流：流量即为最大匹配数；若弧<Xi, Yj>（i∈X，j∈Y）的流量非零，它就是一条匹配边。
二部图最大匹配问题解决。
那么二部图的最佳匹配问题又如何？
仍然按照上述方法构图。同时令原图中弧的费用保持不变；新增弧的费用置为0。然后以S’为源点、T’为汇点求最小费用最大流即可。最大流的费用即为原二部图最佳匹配的费用。
网络应用
将一连串的水管绘画成一个网络。每条水管有一特定的阔度，因此只可以保持一特定的水流量。当任何水管汇合，流入汇流点的总水量必须等于流出的水量，否则我们会很快地缺水，或者我们会团积水。我们有一个作为源点的入水口，和一个作为汇点的出水口。一道流便是一条由源点到汇点而使从出水口流出的总水量一致的可能路径。直观地，一个网络的总流量是水从出口流出的速率。
流可以关于在交通网络上的人或物质，或电力分配系统上的电力。对于任何这样的实物网络，进入任何中途结点的流需要等于离开那结点的流。Bollobás以基尔霍夫电流定律描绘这限制的特性，同时较迟的作者（即 Chartrand）提及它在某些守恒方程的普遍化。
在生态学中也可找到流网络的应用：当考虑在食物网中不同组织之间养料及能量的流，流网络便自然地产生。与这些网络有联繋的数学问题和那些液体流或交通流网络中所产生的难题有很大分别。由 Robert Ulanowicz 及其他人发展的生态系统网络分析领域包含使用信息论及热力学的概念去研究这些网络随时间的演变。

---