网络流
基础
最大流问题的解决一般基于两种方法，即增广路算法与预流推进算法。
网络
一个连通的赋权有向图D=（V、E、C），其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。
流
网络上的流就是由起点流向终点的可行流
正方向
设P为容量网络中源点到汇点的一条链，由源点s到汇点t的方向就为正方向。
残量网络
在一个图中，残留网络指在既有的容量和已具备的流量条件下，网络中仍然可以继续增大流量的边所组成的网络。
增广路经
在残留网络中的一条从源点s流向汇点t的路径叫做一条增广路。
割
图的割可以用来表示对图的一个划分，将原图 G=(V,E)的顶点集 V 分为 S、T 两部分，让源点 s 在 S 中，汇点 t 在 T 中，能够通过 S、T 间的最大净流量为割(S,T)的容量，最小割为图中具有最小容量的割。
最大流
增广路算法
利用不断寻找增广路并在其上对流量进行更新的方法寻找网络的最大流。
每次用BFS找一条最短的增广路径，然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。当没有增广路时，算法停止，此时的流就是最大流。
最大流最小割定理：
在网络的一个流量状态下，通过图的任意一个割的流量都与该流量相同，所以具有最小容量的割的的容量就是该图的流量的最大值即最大流。
