网络流算法在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。
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。