下载文档原格式
⽹络流算法2018-03-13 19:02:13在图论中，⽹络流（英语：Network flow）是指在⼀个每条边都有容量（capacity）的有向图分配流，使⼀条边的流量不会超过它的容量。
通常在运筹学中，有向图称为⽹络。
顶点称为节点（node）⽽边称为弧（arc）。
⼀道流必须匹配⼀个结点的进出的流量相同的限制，除⾮这是⼀个源点（source）──有较多向外的流，或是⼀个汇点（sink）──有较多向内的流。
⼀个⽹络可以⽤来模拟道路系统的交通量、管中的液体、电路中的电流或类似⼀些东西在⼀个结点的⽹络中游动的任何事物。
⼀、最⼤流最⼩割定理最⼤流最⼩割定理提供了对于⼀个⽹络流，从源点到⽬标点的最⼤的流量等于最⼩割的每⼀条边的和。
这个定理说明，当⽹络达到最⼤流时，会有⼀个割集，这个割集中的所有边都达到饱和状态。
这等价于在⽹络中再也找不到⼀个从s到t的增⼴路径。
因为只要能找到⼀条增⼴路径，这条增⼴路径肯定要经过最⼩割集中的⼀条边，否则这个割集就不能称之为割集了。
既然这个割集中所有的边都饱和了，因此也就不会存在这样的增⼴路径了。
这个定理的意义在于给我们指明了⽅向：任何算法，只要最后能达到“再也找不到⼀条增⼴路径”，就可以说明这个算法最后达到了最⼤流。
⼆、最⼤流问题在优化理论中,最⼤流问题涉及到在⼀个单源点、单汇点的⽹络流中找到⼀条最⼤的流。
最⼤流问题可以被看作是⼀个更复杂的⽹络流问题（如循环问题（circulation problem））的特殊情况,。
s-t流（从源点s到汇点t）的最⼤值等于s-t割的最⼩容量，这被称为最⼤流最⼩割定理。
下⾯举例来说明这个问题：问题描述：给定⼀个有向图G=(V,E)，把图中的边看作管道，每条边上有⼀个权值，表⽰该管道的流量上限。
给定源点s和汇点t，现在假设在s处有⼀个⽔源，t处有⼀个蓄⽔池，问从s到t的最⼤⽔流量是多少。
这个问题有如下的⼀些限制：容量限制：也就是在每条通路上的流量都不能超过其capacity。
最大流问题的求解方法及应用
最大流问题，是指在一个有向图中，从源点 s 到汇点 t 的最大
流量。
在实际应用中，最大流问题往往用于描述网络传输、油管输送等流量分配问题。
求解最大流问题的方法包括以下几种：
1. 网络流算法：这是一种基于图论和线性规划的算法。
通过构建网络流图，将最大流问题转化为最小割问题，再利用线性规划求解最小割问题的对偶问题来求解最大流问题。
2. 增广路算法：这是一种经典的最大流算法，其基本思想是不断找到增广路径，即从源点 s 到汇点 t 的一条路径，沿途边权
均有剩余容量，使得该路径上的边的剩余容量中的最小值最大化，最终得到最大流。
3. 矩阵树定理：这是一种基于图论和矩阵运算的算法，适用于有向图和无向图。
通过计算图的拉普拉斯矩阵的行列式等方法，求得图的生成树个数，从而计算最大流。
4. Dinic算法：是对增广路算法的改进。
在增广路算法中，每
次查找增广路径的过程需要遍历整个图，为了提高效率，
Dinic算法引入了分层图的概念，将图分层之后只在图的一层
中查找增广路径，最终求得最大流。
这些方法在实际应用中常常被用来解决路由选择、网络流量优化、模拟电路分析等问题。
例如，最大流可以被用来优化数据传输、流水线设计、流量管道的运营和管理，提高资源利用率和数据传输速度。
数学建模中的网络流问题与算法数学建模是一种将实际问题转化为数学模型，并通过数学方法求解的过程。
在实际问题中，常常需要解决网络流问题，即在网络中如何最大化或最小化流量的分配问题。
网络流算法是解决网络流问题的重要工具。
本文将分析网络流问题的基本概念和应用，并介绍常用的网络流算法。
一、网络流问题的基本概念1.网络流模型网络流模型是指将实际问题转化为图中节点和边的组合，并进行流量分配的问题。
其中，节点表示供给和需求单位，边表示可以流动的路径。
网络流模型常用于物流、运输、通信等领域的问题求解。
2.流量网络流问题中的流量表示在网络中通过路径的物理量。
流量可以是货物的数量、电信系统中数据的传输速率等。
流量可以是有向的或无向的，有时还会带有容量的限制。
3.割在网络中，将节点集划分为两个互不相交的子集，这个划分称为割。
割可以用来描述流量限制或流量约束。
在最小割问题中，割的容量描述了限制在网络中流量的最小边数。
二、网络流问题的应用1.最大流问题最大流问题是网络流问题中的一种，目标是在网络中从源节点到汇节点找到可行的最大流量。
最大流算法可以用于求解交通流优化问题、工作调度等。
2.最小割问题最小割问题是网络流问题中的另一种形式，目标是在网络中找到一个割，使得割的边数最小。
最小割算法可以用于求解电力系统分析、路网规划等问题。
3.多组源汇问题多组源汇问题是一种特殊的网络流问题，可以有多个源节点和汇节点，并且在每个节点之间还有容量限制。
多组源汇问题在物流调度、通信网络优化等领域有广泛应用。
三、常用的网络流算法1.最大流算法常用的最大流算法有Ford-Fulkerson算法、Edmonds-Karp算法和Dinic算法等。
这些算法利用增广路径或增广路进行迭代，直到无法找到增广路径为止。
2.最小割算法最小割算法有Ford-Fulkerson算法和推进-重贴算法等。
这些算法通过不断削减割的容量来求解最小割问题。
3.二部图匹配算法二部图匹配算法可以看做是一种特殊的网络流算法。
学习笔记——⽹络流⼀、⽹络流的概念⽹络流：所有弧上流量的集合f=f(u,v)，称为该流量⽹络的⼀个⽹络流。
定义：带权的有向图G=(V,E)，满⾜以下条件，则称为⽹络流图。
：1.有且仅有⼀个⼊度为0的顶点$ s ，称s$为源点。
2.有且仅有⼀个出度为0的顶点$ t ，称t$为汇点。
3.每条边的权值都为⾮负数，称为该边的容量，记作c(u,v)。
弧的流量：通过流量⽹络G中的每条弧(u,v)上的实际流量（简称流量），记作f(u,v)。
性质对于任意⼀个时刻，设f(u,v)为实际流量，则整个图G的流⽹络满⾜3个性质：1.流量限制：对于任意$u,v \in V ，f(u,v) \le c(u,v)$。
2.反对称性：对于任意$u,v \in V ，f(u,v) = -f(v,u)，即从u到v的流量等于从v到u$的流量的相反数。
3.流守恒性：对于任意$u \in V ，若u不为S或T，⼀定有\sum f(u,v) = 0，其中(u,v) \in V 。
简单来说就是流⼊u点的流量等于流出u点的流量，因为u$点本⾝不会“制造”和“消耗”流量。
可⾏流：在流量⽹络G中满⾜以下条件的⽹络流f，称为可⾏流1.弧流量限制条件:0≤f(u,v)≤c(u,v)2.平衡条件：流⼊u点的流量等于流出u点的流量（源点和汇点除外）举个栗⼦：上图中可⾏流为:2+1+2=5零流：⽹络流上每条弧的流量都为0。
伪流：如果⼀个⽹络流只满⾜弧流量限制条件，不满⾜平衡条件，则这种⽹络流为伪流或容量可⾏流(预流推进算法有⽤)。
最⼤流最⼩割定理：在容量⽹络中，满⾜弧流量限制条件和平衡条件并且具有最⼤流量的可⾏流，称为⽹络最⼤流（简称最⼤流）。
最⼤流对于⽹络流图G，流量最⼤的可⾏流f，称为最⼤流弧的类型1.饱和弧：f(u,v)=c(u,v)2.⾮饱和弧：f(u,v)<c(u,v)3.零弧：f(u,v)=04.⾮零弧：f(u,v)>0链在流量⽹络中，相邻两个顶点之间有⼀条弧（不要求所有弧的⽅向都和链的⽅向相同），则称该顶点序列(u1、u2......u n)为⼀条链。
网络流算法的实现与应用网络流算法是图论中的一类重要算法，通过对网络中流的分配与调度来解决相关问题。
本文将探讨网络流算法的实现原理与应用场景。
一、网络流算法概述网络流算法主要处理的是“网络流”问题，即在一个图论模型中，寻找一种边的流动方式，使得源点到汇点的流量最大化或者达到某种要求。
常见的网络流算法包括最大流算法、最小割算法和最大权闭合子图算法等。
二、网络流算法的实现1. 最大流算法最大流算法旨在寻找网络中从源点到汇点的最大流量。
其中，最常用的算法是Edmonds-Karp算法，它是基于BFS（广度优先搜索）的增广路径寻找。
在实现过程中，可以使用图的邻接矩阵或邻接表来表示网络，利用算法的迭代思想不断寻找增广路径，并同时更新网络中的流量与残余容量，直到无法找到增广路径为止。
2. 最小割算法最小割算法用于求解网络中的最小割问题，即将网络分割为两个部分，使得切开的边的权值之和最小。
其中，Ford-Fulkerson算法是经典的最小割算法之一。
在实现过程中，可以通过DFS（深度优先搜索）或BFS寻找增广路径，并不断更新割与割集，直到最小割的权值无法再减小。
3. 最大权闭合子图算法最大权闭合子图算法用于求解有向图中的最大权闭合子图问题，其中闭合子图是指若干个节点的集合，对于任意一对节点u和v，如果存在一条从u到v的有向边，则u必定属于闭合子图中。
在实现过程中，可以使用Bellman-Ford算法来寻找最短路径，并通过路径上的正权重进行子图的扩展，最终得到最大权闭合子图。
三、网络流算法的应用网络流算法具有广泛的应用场景，以下介绍几个常见的应用领域：1. 传输网络规划网络流算法可以用于解决最大流问题，从而优化传输网络的规划。
例如，在通信网络中，可以通过最大流算法来确定最大传输容量，从而提高网络的传输效率。
2. 作业调度网络流算法可以用于解决作业调度问题，例如在工业生产中，通过最大流算法来确定最大的作业处理能力，从而提高生产效率。
网络流算法在移动通信网络中的应用第一章简介移动通信网络是现代社会中必不可少的基础设施，它连接着人们的生活和工作。
为了提高移动通信网络的性能和效率，网络流算法被广泛应用于移动通信网络的设计和优化中。
本文将介绍网络流算法在移动通信网络中的应用，探讨其在优化网络资源分配、减少网络拥塞、提高网络容量等方面的作用。
第二章网络流算法的基本原理网络流算法是一种通过建立网络模型来解决网络中流量分配问题的方法。
它将网络视为一个有向图，节点代表网络中的交通节点，边表示节点之间的连接，边上的权重表示流量的限制或代价。
网络流算法通过在图中寻找一条从源节点到汇节点的最大流或最小割来解决问题。
第三章移动通信网络中的资源分配问题在移动通信网络中，资源分配是一个重要的问题。
网络流算法可以用于优化资源的分配，使得网络的效率最大化。
例如，在无线电网络中，网络流算法可以通过计算不同用户之间的最大流来决定无线频谱的分配，从而提高网络的容量和性能。
第四章移动通信网络中的路由问题路由是移动通信网络中的关键问题，它决定了数据包从源节点到目的节点的路径。
网络流算法可以用于解决路由问题，使得数据包的传输路径最优化。
例如，在移动电话网络中，网络流算法可以通过计算源节点到目的节点的最小割来确定数据包的路由，从而减少网络拥塞和延迟。
第五章移动通信网络中的拥塞控制问题拥塞控制是移动通信网络中常见的问题，当网络中的流量超过网络容量时，会导致网络拥塞和性能下降。
网络流算法可以用于拥塞控制，通过调整流量分配来减少网络的拥塞。
例如，在流媒体传输中，网络流算法可以通过在网络中动态调整流量的分配，从而避免网络拥塞和数据丢失。
第六章移动通信网络中的容量规划问题容量规划是移动通信网络中的重要问题，它涉及到网络资源的合理分配和规划。
网络流算法可以用于容量规划，通过计算网络中不同节点之间的最大流来确定网络的容量需求，从而优化网络资源的分配。
例如，在移动数据网络中，网络流算法可以用于预测不同基站之间的流量分布，从而帮助运营商合理规划网络容量和资源。
网络流算法（NetworkFlow）网络流算法，是指寻找网络流问题的解的算法，它是一类重要的组合优化问题，被广泛应用于计算机科学及工程领域。
网络流是个有向图，它模拟了许多实际问题，如输电方案、货物运输、油管输送和信息传输等。
网络流算法的目的是在给定的网络流中，尽可能地将流量从源点流向汇点，同时满足各个节点的容量约束和流量平衡约束。
本文将介绍网络流模型的构建和基本算法。
一、网络流模型的构建网络流模型是一个有向图G=(V,E)，其中V表示节点集合，E表示边集合。
每条边都有一个容量c(e)表示其流量的最大值。
设源点为s，汇点为t，则网络流模型可以表示为一个三元组(N,s,t)，即：N=(V,E) s∈V t∈V s≠t在网络流模型中，源点始终是起点，汇点始终是终点。
我们在模型中引入一个源汇节点s'和汇源节点t'，并连接源点和汇点，得到源汇图G'=(V,E')，其中：E'=E∪{(s',s,c(s,t))}∪{(t,t',c(s,t))}即，在原图的基础上，加入两个新的虚拟节点s'和t'，并连接到源点和汇点。
这样构造的网络流模型中，所有的节点都满足容量和流量平衡约束。
在网络流问题中，我们需要求解最大流或最小割，以满足约束条件，并且尽可能地提高网络的利用率。
二、网络流的基本概念和算法1. 流量和容量网络流图中，首先需要确定每条边的容量和流量。
流量指的是通过该边的流量大小，容量指的是该边能够承受的最大流量。
在网络流模型中，每条边的容量是一个正实数，而流量可以是任意实数。
流量和容量通常表示为f(e)和c(e)。
2. 割在网络流模型中，割是一种对源汇图做出的划分，其中源点s和汇点t被分为两个集合S和T。
网络流通过割的概念来定义障碍物，即对流量的限制。
在网络流图中，割C(S,T)是指将源点s和汇点t割成两部分的划分，C(S,T)满足：s∈S t∈T S∩T=∅根据割的定义，可将所有割分为最小割和最大割。
⽹络流（最⼤流-Dinic算法）⽹络流定义 在图论中，⽹络流（Network flow）是指在⼀个每条边都有容量（Capacity）的有向图分配流，使⼀条边的流量不会超过它的容量。
通常在运筹学中，有向图称为⽹络。
顶点称为节点（Node）⽽边称为弧（Arc）。
⼀道流必须匹配⼀个结点的进出的流量相同的限制，除⾮这是⼀个源点（Source）──有较多向外的流，或是⼀个汇点（Sink）──有较多向内的流。
⼀个⽹络可以⽤来模拟道路系统的交通量、管中的液体、电路中的电流或类似⼀些东西在⼀个结点的⽹络中游动的任何事物。
————维基百科 最⼤流 正如可以通过将道路交通图模型化为有向图来找到从⼀个城市到另⼀个城市之间的最短路径，我们也可以将⼀个有向图看做是⼀个“流⽹络”并使⽤它来回答关于物料流动⽅⾯的问题。
设想⼀种物料从产⽣它的源结点经过⼀个系统，流向消耗该物料的汇点这样⼀个过程。
源结点以某种稳定的速率⽣成物料，汇点则以同样的速率消耗物料。
从直观上看，物料在系统中任何⼀个点上的“流量”就是物料移动的速率。
这种流⽹络可以⽤来建模很多实际问题，包括液体在管道中的流动、装配线上部件的流动、电⽹中电流的流动和通信⽹络中信息的流动。
我们可以把流⽹络中每条有向边看做是物料的⼀个流通通道。
每条通道有限定的容量，是物料流经该通道时的最⼤速率，如⼀条管道每⼩时可以流过200加仑的液体。
流⽹络中的结点则是通道的连接点。
除了源结点和终结点外，物料在其他结点上只是流过，并不积累或聚集。
换句话说，物料进⼊⼀个结点速率必须与其离开该结点的速率相等。
这个性质称为“流量守恒”，这⾥的流量守恒与Kirchhoff电流定律等价。
在最⼤流问题中，我们希望在不违反任何容量限制的情况下，计算出从源结点运送物料到汇点的最⼤速率。
这是与流⽹络有关的所有问题中最简单的问题之⼀().，这个问题可以由⾼效的算法解决。
⽽且，最⼤流算法中的⼀些基本技巧可以⽤来解决其他⽹络流问题。
图论中网络流算法及优化图论中的网络流算法及优化一、引言网络流算法是图论中的重要分支，它被广泛应用于解决各种实际问题，如交通流、电力传输等。
本文将介绍网络流算法的基本概念和常用的优化方法。
二、网络流算法1. 最大流问题最大流问题是网络流算法中最基本的问题之一。
其目标是在给定网络中找到从源点到汇点的最大流量。
常用的解决方法包括：（1）Ford-Fulkerson算法：该算法通过不断寻找增广路径来增加流量，直到无法再找到增广路径为止。
（2）Edmonds-Karp算法：在Ford-Fulkerson算法的基础上，引入了BFS搜索策略来寻找增广路径，提高了算法的效率。
2. 最小割问题最小割问题与最大流问题密切相关。
最小割是指将网络划分为两个部分，并且使得网络中横跨这两个部分的边的权重之和最小。
常用的解决方法包括：（1）Ford-Fulkerson算法：该算法在求解最大流问题的同时可以得到最小割的结果。
（2）Dinic算法：通过构造分层图和阻塞流的概念，提高了算法的效率。
三、网络流算法的优化网络流算法在实际应用中可能面临大规模问题的挑战，因此需要采用一些优化方法来提高算法的效率和准确性。
1. 改进的数据结构使用合适的数据结构可以减少算法的时间和空间复杂度。
例如，使用邻接矩阵或邻接表来存储图的信息，选择合适的数据结构来表示流量、残余网络等。
2. 快速增广快速增广是一种对增广路径进行选择的策略，可以减少算法的时间复杂度。
常见的快速增广方法包括Dinic算法和HLPP算法。
3. 预流推进预流推进是一种改进的增广策略，它通过将多余的流量分配到其他边上，减少了增广路径的数量。
常用的预流推进算法包括Push-Relabel 算法和Preflow-Push算法。
4. 分阶段算法对于大规模的网络流问题，可以采用分阶段算法来解决。
分阶段算法将整个问题划分为多个子问题，并结合贪心、动态规划等方法进行求解。
四、总结网络流算法在图论中扮演着重要的角色，可以解决许多实际问题。
网络流算法在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。
50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。
在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。
本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。
［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。
产品经过交通网从v1到v4。
现在要求制定一个运输方案使从v1到v4的产品数量最多。
一、基本概念及相关定理1)网络与网络流定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。
如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。
所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。
如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。
2)可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。
因此有：定义2 满足下列条件(1)容量约束：0≤fij≤cij，(vi,vj)∈E，(2)守恒条件对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。
网络N中流值最大的流f*称为N的最大流。
3)可增广路径所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。
定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：(1)在p 上的所有前向弧(vi →vj)都是非饱和弧，即0≤fij<cij(2)在p 上的所有后向弧(vi ←vj)都是非零弧，即0<fij≤cij则称p 为(关于可行流f 的)一条可增广路径。
V ,E,C,V S ,V T : 从V s 开始到Vt 建立起的一个流的网络。
C 容量--（Cvi,Cvj ）简写成C i,jF i,j 表示流量。
<1>可行流：对于中间点，流入量=流出量；源点与汇点：源点的净流出量Vs(f)=-Vt(f) 汇点的净流入量,f 称为这个网络的可行流。
并将源点S 的净流量称为流值。
记：vi 点的净流出量与净流入的差有三种: =0中间点i=s, =vf i=t -vf(f)网络N 中流值最大的流f*称为N 的最大流 <3>可增广路径：是指在这条路径上的流可以修改，通过修改，让他的流量增大。
⎪⎩⎪⎨⎧=-≠==-∑∑∈∈t i f v t s i s i f v f f i j i j v B v ji v A v ij )(,0)()()(0020θ(i)=表示顶点i可以增广的流量。
θ(t)-><1>最大流最小割定理：在一个网络N中，从Vs到Vt最大流的容量等于分离Vs,Vt的最小割的容量。
●给源点S+,θ(s)=∞找出与已标记顶点相连（有直接边）的未标记的顶点进行标记1、(i,j)是i-→j前向弧且饱和（fij=cij），则j不标记2、（i,j)是i→j前向弧且不饱和(fij<cij)，则j标记为i+,min(θ(i),cij-fij)3、(j,i)是反向弧j-→i 且fji=0则j不标记4、(j,i)是反向弧j-→i 且fji>0则j: i-,min(θ(i),fji)直到图中标记到了Vt，，就得到了一条增广路径θ(t)。
<2>汇点的f,是所有增广路径上标记顶点流量f的最小值θ(t)。
从汇点回溯到源点，如果从顶点j回溯到i，只要看j的标记如果+,则把fij=fij+θ(t);如果是-,(说明是反向弧) fji=fji-θ(t);多次增广以后，直到不能再继续标记了，就得到最大流。
***最大流=源点的所有净输出量=汇点的所有净输入量。
***最小割=是从源点开始可以进行增广的所有顶点集合+剩下顶点的集合。
--》经过增广以后得到：红色圈为：包含Vs的不能再增广的A割,绿色为包含Vt的顶点集合。
则有最大流最小割的定义知：割集={每条的起点，终点}={(3,t).(2,4)}最大流（最小割的流量）=上面的割集的输出流总量=5+9=14 注意：6是输入，不是计入最大流的值。
(4)割及其容量定义4 如果A是V的一个子集，A-=V-A，s∈A，t∈A-，则称边集(A，A-)为网络N的一个割，显然，若把某一割的弧从网络中丢去，则从vs到vt就不存在路。
所以直观上讲，割是从vi到vj的必经之道。
定义5 给一割(A，A-)，把其中所有弧的容量之和称为这个割的容量，记为c(A，A-)，即c(A，A-)=∑c(e)网络N中容量最小的割(A*，A*-)称为N的最小割。
不难证明，任何一个可行流的流量v(f)都不会超过任一割的容量，即v(f)≤c(A，A-)例如，图4-2中，若A={s}，(A，A-)={(s，v3)，(s，v2)}，c(A，A-)=4+3=7。
A(顶点的一个子集),A-(所有的顶点减-A)，A中的顶点有直接边的到（A的补集）容量之和。
C（A，A-）=4+3=7A（VS）---A-（Vt）Vi,Vj满足：Vi属于A，Vj属于A-***反向边不行，必须是从Vi到Vj即Vj到Vi不行•第一步：标号过程，找一条增广链–1、给源点s标号[s+,q(s)=∞]，表示从s 点有无限流出潜力–2、找出与已标号节点i相邻的所有未标号节点j，若–(1) (i, j)是前向弧且饱和，则节点j不标号；–(2) (i, j)是前向弧且未饱和，则节点j标号为[i+,q(j)]，表示从节点i正向流出，可增广q(j)=min[q(i),c ij-f ij] ；–(3) (j, i)是后向弧，若f ji=0，则节点j不标号；–(4) (j, i)是后向弧，若f ji>0，则节点j标号为[i-,q(j)]，表示从节点j流向i，可增广q(j)=min[q(i),f ji] ；(5)有关定理定理1 当且仅当不存在关于f*的增广路径，可行流f*为最大流。
证明必要性：若f*是最大流，设N中存在关于f*的增广路径p，令：Q=min{min(cij-fij)，minf*ij}由增广路径定义可知，Q>0，再令：f**ij = f*ij+Q (vi，vj)∈P的前向弧的集合f**ij = f*ij-Q (vi，vj)∈P的后向弧的集合f**ij = f*ij (vi，vj)不属于P的集合不难证明{f**ij}是—可行流，且v(f**)=v(f*)+Q>v(f*)。
这与f*是最大流假设矛盾，必要性证毕。
证明充分性：设N中不存在关于f*的增广路径，证明f*是最大流。
我们利用下面的方法来定义A*。
令vs∈A*若vi∈A*，且fij<cij，则令vj∈A*；若vi∈A*，且fji>0，则令vj∈A*。
因为不存在关于f*的增广路径，故vt不属于A*。
记A*-=V-A*，于是得到一个割(A*，A*-)，显然有f*ij=cij，(vi，vj)∈(A*，A*-)f*ij=0，(vi，vj)∈(A*-，A*)所以v(f*)=c(A*，A*-)。
于是f*必是最大流，定理得证。
由上述证明中可得，若f*是最大流，则网络中必存在一个割集c(A*，A*-)，使得v(f*)=c(A*，A*-)。
于是有以下重要定理。
定理2 最大流最小割定理：在一个网络N中，从vs到vt最大流的容量等于分离vs，vt的最小割的容量。
codeforces 164 C 费用流这是我在codeforces上做的第一个网络流的题目，思维还不错，讲讲题意：给你n个任务，k个机器，n个任务的起始时间，持续时间，完成任务的获利每个机器可以完成任何一项任务，但是同一时刻只能完成一项任务，一旦某台机器在完成某项任务时，直到任务结束，这台机器都不能去做其他任务最后问你当获利最大时，应该安排那些机器工作，即输出方案刚看到题就想到一个贪心的思路，如果一台机器完成了某项工作，它应该继续去完成接下来最先开始的工作，感觉有点像网络流里面的建图啊，于是继续往这个方向YY，我擦，结果还真可以网络流来搞。
具体建图方法：新建源汇S T‘对任务按照起始时间s按升序排序拆点：u 向u'连一条边容量为1 费用为-c,u' 向T连一条边容量为inf 费用为0；如果任务u完成后接下来最先开始的是任务v则从u' 向v连一条边，容量inf 费用0.另外，任务从前往后具有传递性，所以必须是第i个任务向第i+1个任务建边，容量为inf 最后，限制一下起始点向第一个任务的流量即可（即K）my code。
