网络流解析——最大流EdmondsKarp算法

原理并不复杂，但存在的疑惑主要集中在反向边的引入，以下篇幅作以讲解。
首先假设一不存在TS边的单源有向加权图。
（所谓“TS边”即是指对于任一割，方向为T->S的边）
类似下图（1为S，6为T，边权（容量）均为10）

此时若求解最大流问题（具体命题省略），按照EdmondsKarp算法，作出其残量网络。
为了解释反向边的作用，我们考虑不使用反向边的情况下，所得出的结果。
下图为不包含反向边的残量网络。

每条原始图的边流量初始化为0，相应残量则为10。
如此只要我们对于每条增广路（连接S与T的路）进行增广（将增广路的流量灌到最大限度），最后所有增广路灌流量相加即为最大流结果。
以上都十分直观。
引入割的概念
割：通俗理解，一个图或网络的割，表示一个切面或切线，将图或网络分为分别包含源点和漏点的两个子集，该切线或切面与网络相交的楞或边的集合，称为图像的割。（百度百科）
注意，其中不包含T->S边。
由定义，割其实是 Σ cap,而一定有 Σ flow<= Σ cap

由图可知，最大流=最小割。
而倘若遇到下图情况，头疼了

如图，如果执行bfs一次扫描到增广路1->2->4->6，流量总量累加10，得到的残量网络无法继续进行增广，那么算法返回最大流为10。
然而实际上最大流是20，显然该算法是有问题的。
问题出在哪里呢？
显然每当算法结束（即使最后结果出错）时，所得到的残量网络必然不存在S->T边，而可能存在T->S边。

造成残量网络这种结果的是原网络中所有S->T路流量均达到容量大小，而T-S路却不一定存在。
类比最大流最小割原理，此时达到容量的S->T边集等于最小割，也就是我们要的最大流。
因此不论结果是否有错，结果中总能包括最大流，且错误就出在T->S边的保留上 。
显然对于最大流，我们不想要在所有S->T边流量最大的基础上，有回流的T->S边。
因此就需要引入反向边了。
我们为所有边设置反向边，并将其流量与正向边同步。为了保持T->S边流量为0，每当由于增广操作，T->S边流量上升，其反向边也同步上涨，而显然在残量网络中反向边是沿S->T方向的，这就又出现了一条增广路，计算机对此无法容忍，下调它的流量，我们的T->S边流量也随之回到了0，达到了目的。
以上便是对反向边方法的详细解释，对于某些基本概念不清的话需要先熟悉一下EdmondsKarp算法。