来源：http://blog.csdn.net/qiankun1993/article/details/6782838
来源: http://blog.csdn.net/leolin_/article/details/7202691
http://wenku.baidu.com/view/e117225277232f60ddcca187.html?re=view
来源：http://blog.csdn.net/y990041769/article/details/21026445
来源：http://blog.csdn.net/wall_f/article/details/8207595
网络流
首先来看一下基本的网络流模型。
有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点，通常规定为1号点。另一个点也很特殊，只进不出，叫做汇点，通常规定为n号点。每条有向边上有两个量，容量和流量，从i到j的容量通常用 c[I,j]表示（capacity）,流量则通常是f[I,j] （flow）。通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。很显然的，流量<=容量。而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有”进入”他们的流量和等于所有从他本身”出去”的流量。
最大流算法
增广路算法
想法：
首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个可行流。一个最简单的例子就是，零流，即所有的流量都是0的流。
我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta，一定可以保证这个流依然是可行流，这是显然的。
这样我们就得到了一个更大的流，他的流量是之前的流量+delta，而这条路就叫做增广路。
我们不断地从起点开始寻找增广路，每次都对其进行增广，直到源点和汇点不连通，也就是找不到增广路为止。当找不到增广路的时候，当前的流量就是最大流，这个结论非常重要。
寻找增广路的时候我们可以简单的从源点开始做bfs，并不断修改这条路上的delta量，直到找到源点或者找不到增广路。
网络流的三个性质：
1、容量限制: f[u,v]<=c[u,v]
2、反对称性：f[u,v] = - f[v,u]
3、流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。
只要满足这三个性质,就是一个合法的网络流.
最大流问题，就是求在满足网络流性质的情况下，源点 s 到汇点 t 的最大流量。
**残量网络
为了更方便算法的实现，一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。
r(u,v) = c(u,v) – f(u,v)
通俗地讲：就是对于某一条边（也称弧），还能再有多少流量经过。
Gf 残量网络,Ef 表示残量网络的边集.
这是上面图的一个残量网络。残量网络（如果网络中一条边的容量为0,则认为这条边不在残量网络中。
r(s,v1)=0,所以就不画出来了。另外举个例子：r(v1,s) = c(v1,s) – f(v1,s) = 0 – (-f(s,v1)) = f(s,v1) = 4.
其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。
但是从v1到s不是和原网络中的弧的方向相反吗？显然“从v1到s还可以增加4单位流量”这条信息毫无意义。那么，有必要建立这些后向弧吗？
显然，第1个图中的画出来的不是一个最大流。
但是，如果我们把s -> v2 -> v1 -> t这条路径经过的弧的流量都增加2,就得到了该网络的最大流。
注意到这条路径经过了一条后向弧:(v2,v1)。
如果不设立后向弧，算法就不能发现这条路径。
**从本质上说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为（让2单位的流从v1流到v2)
正向弧的作用：说明该路径的流量还可以继续增加
反向弧的作用：说明这条路径已经使用的流量。也就是这条边最多能退回多少流量。通过走反向弧，能实现流量的退回
**增广路
增广路定义：在残量网络中的一条从s通往t的路径，其中任意一条弧(u,v)，都有r[u,v]>0。
如图绿色的即为一条增广路。
所谓的增广路：路上每个r[u][v]>0，其实也就说明这条路的流量还可以增加。我们的算法要找到不存在增广路为止
最大流最小割定理：一个流是最大流，当且仅当它的残留网络不包含增广路径。
流网络的割（S，T）（类似二分图？）将V划分为 S 和 T = V – S两部分，使得 s ∈ S，t ∈ T。如果 f 是一个流，则穿过割 （S，T）的净流被定义为 f (S，T）。割（S，T）的容量为 c（S，T）。一个网络的最小割就是网络中所有割中最小容量的割。
**增广路算法当我们第二次的增广路走 3→2 这条反向边的时候，就相当于把 2→3 这条正向边已经是用了的流量给“退”了回去*（也再次说明了反向边的意义：已经使用的流量），不走 2→3 这条路，而改走从 2 点出发的其他的路也就是 2→4。（有人问如果这里没有 2→4 怎么办，这时假如没有 2→4 这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在 3→4 上的流量由 1→3→4 这条路来“接管”。而最终 2→3 这条路正向流量1，反向流量1，等于没有流量。反向边的作用就是给程序一个可以后悔的机会。
每次更新一个路径就可以了，因为路径是形成一个流的基本单位。
增广路算法：每次用BFS找一条最短的增广路径（spfa），然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。当没有增广路时（对于spfa来说，就是dis[N]=INF），算法停止，此时的流就是最大流。
**增广路算法的效率
设n = |V|, m = |E|
每次增广都是一次BFS,效率为O(m),而在最坏的情况下需要（n-2增广。（即除源点和汇点外其他点都没有连通，所有点都只和s与t连通）
所以,总共的时间复杂度为O(m*n)，所以在稀疏图中效率还是比较高的。
Edge结构的构造函数
<p><span style="font-size:14px;font-weight: normal;">struct Edge{
int from,to,flow,cap;
}
Edge(int a,int b,int c,int d):from(a),to(b),flow(c),cap(d){
}
</span></p>
EK算法的核心是用BFS来搜索增广路
反复寻找源点s到汇点t之间的增广路径，若有，找出增广路径上每一段[容量-流量]的最小值delta，若无，则结束。
在寻找增广路径时，可以用BFS来找，并且更新残留网络的值(涉及到反向边)。
而找到delta后，则使最大流值加上delta，更新为当前的最大流值。
这么一个图，求源点1，到汇点4的最大流
由于我是通过模版真正理解ek的含义，所以先上代码，通过分析代码，来详细叙述ek算法
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 201;
int INF = 0x7fffffff;
int capacity[maxn][maxn]; //记录残留网络的容量
int flow[maxn]; //标记从源点到当前节点实际还剩多少流量可用
int pre[maxn]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
int M,N;
queue<int> myqueue;
int BFS(int src,int des){
while(!myqueue.empty()) myqueue.pop();
for(int i=1;i<=M;i++) pre[i]=-1;
pre[src]=0;
flow[src]=INF;
myqueue.push(src);
while(!myqueue.empty()){
int current=myqueue.front();
myqueue.pop();
if(current==des) break;
for(int i=1;i<=M;i++){
if(i!=src && pre[i]==-1 && capacity[current][i]>0){
flow[i]=min(flow[current],capacity[current][i]);
pre[i]=current;
myqueue.push(i);
}
}
}
if(pre[des]==-1) return -1;
return flow[des];
}
int EK_maxflow(int src,int des){
int inc=0;
int max_flow=0;
while((inc=BFS(src,des))!=-1){
max_flow+=inc;
int nextV=des;
int preV=pre[des];
while(nextV!=src){
capacity[preV][nextV]-=inc;
capacity[nextV][preV]+=inc;
nextV=preV;
preV=pre[preV];
}
}
return max_flow;
}
int main()
{
int a,b,c;
while(cin>>N>>M)//N为边，M为点
{
memset(capacity,0,sizeof(capacity));
memset(flow,0,sizeof(flow));//其实flow不用初始化
for(int i=0;i<N;++i)
{
cin>>a>>b>>c;
if(a == b) //考虑起点终点相同的情况
continue;
capacity[a][b] +=c; //此处注意可能出现多条同一起点终点的情况
}//多边应该用加
cout<<EK_maxflow(1,M)<<endl;
}
return 0;
}
显而易见capacity存变的流量，进行ek求解
对于BFS找增广路：
1. flow[1]=INF，pre[1]=0;
源点1进队列，开始找增广路，capacity[1][2]=40>0，则flow[2]=min(flow[1],40)=40;
capacity[1][4]=20>0,则flow[4]=min(flow[1],20)=20;
capacity[2][3]=30>0,则flow[3]=min(folw[2]=40，30)=30；
capacity[2][4]=30,但是pre[4]=1(已经在capacity[1][4]这遍历过4号点了)
capacity[3][4].....
当index=4（汇点），结束增广路的寻找
传递回increasement（该路径的流），利用前驱pre寻找路径
路径也自然变成了这样：
2.flow[1]=INF，pre[1]=0;
源点1进队列，开始找增广路，capacity[1][2]=40>0，则flow[2]=min(flow[1],40)=40;
capacity[1][4]=0!>0,跳过
capacity[2][3]=30>0,则flow[3]=min(folw[2]=40，30)=30；
capacity[2][4]=30,pre[4]=2，则flow[2][4]=min(flow[2]=40,20)=20;
capacity[3][4].....
当index=4（汇点），结束增广路的寻找
传递回increasement（该路径的流），利用前驱pre寻找路径
图也被改成
接下来同理
这就是最终完成的图，最终sumflow=20+20+10=50（这个就是最大流的值）
PS，为什么要有反向边呢？
我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。于是我们修改后得到了下面这个流。（图中的数字是容量）
这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。
但这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。
那么我们刚刚的算法问题在哪里呢？问题就在于我们没有给程序一个”后悔”的机会，应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢？回溯搜索吗？那么我们的效率就上升到指数级了。
而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i)，反向边也同样有它的容量。
我们直接来看它是如何解决的：
在第一次找到增广路之后，在把路上每一段的容量减少delta的同时，也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时，inc(c[y,x],delta)
我们来看刚才的例子，在找到1-2-3-4这条增广路之后，把容量修改成如下
这时再找增广路的时候，就会找到1-3-2-4这条可增广量，即delta值为1的可增广路。将这条路增广之后，得到了最大流2。
那么，这么做为什么会是对的呢？我来通俗的解释一下吧。
事实上，当我们第二次的增广路走3-2这条反向边的时候，就相当于把2-3这条正向边已经是用了的流量给”退”了回去，不走2-3这条路，而改走从2点出发的其他的路也就是2-4。（有人问如果这里没有2-4怎么办，这时假如没有2-4这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1，反向流量1，等于没有流量。
（同时，我们之所以可以走3-2这条边，也说明我们可以找到一个从源点到这里的路。通过走3-2这条边，其实是退回了一部分从2到3的流量，让这些流流量通过2-4流出，而退回的流量通过3-4流出，其实是流量的重新分配）
这就是这个算法的精华部分，利用反向边，使程序有了一个后悔和改正的机会。而这个算法和我刚才给出的代码相比只多了一句话而已。
至此，最大流Edmond-Karp算法介绍完毕。
复杂度
O(VE^2)(DFS复杂度V*E)
poj1273裸网络流：
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=220;
int capacity[maxn][maxn];
int pre[maxn];
int flow[maxn];
const int INF=0xfffffff;
queue<int> myqueue;
int N,M;
int BFS(int src,int des){
<span style="color:#ff0000;">while(!myqueue.empty()) myqueue.pop();</span>
for(int i=1;i<=N;i++) pre[i]=-1;
pre[src]=0;
<span style="color:#ff0000;">flow[src]=INF;</span>
myqueue.push(src);
while(!myqueue.empty()){
int current=myqueue.front();
myqueue.pop();
if(current == des) break;
for(int i=1;i<=N;i++){
if(i!=src&&pre[i]==-1&&capacity[current][i]>0){
pre[i]=current;
<span style="color:#ff0000;">flow[i]=min(flow[current],capacity[current][i]);</span>
myqueue.push(i);
}
}
}
if(pre[des]==-1) return -1;
return flow[des];
}
int MaxFlow(int src,int des){
int sum=0;
int inc=0;
while((inc=BFS(src,des))!=-1){
sum+=inc;
int nextV=des;
int preV=pre[des];
while(nextV!=src){
capacity[preV][nextV]-=inc;
capacity[nextV][preV]+=inc;
nextV=preV;
preV=pre[preV];
}
}
return sum;
}
int main(int argc, char const *argv[])
{
while(cin>>M>>N){
memset(capacity,0,sizeof(capacity));
memset(flow,0,sizeof(flow));
int a,b,c;
for(int i=0;i<M;i++){
scanf("%d%d%d",&a,&b,&c);
<span style="color:#ff0000;">capacity[a][b]+=c;</span>
}
printf("%d\n",MaxFlow(1,N) );
}
return 0;
}代码注意：
Dinic算法
为了更好的介绍Dinic算法，我们先来介绍最短增广路算法。
最短增广路算法
1、顶点的层次和层次网络
顶点的层次：在残留网络中，把从源点到顶点u的最短路径长度（该长度仅仅是值路径上边的数目，与容量无关），称为顶点u的层次，记为level(u)。源点Vs的层次为0。
将残留网络中所有的顶点的层次标注出来的过程称为分层。
注意：
（1）对残留网路进行分层后，弧可能有3种可能的情况。
1、从第i层顶点指向第i+1层顶点。
2、从第i层顶点指向第i层顶点。
3、从第i层顶点指向第j层顶点（j < i）。
（2）不存在从第i层顶点指向第i+k层顶点的弧(k>=2)。
（3）并非所有的网络都能分层。
层次网络：对残留网络进行分层后，删去比汇点Vt层次更高的顶点和与汇点Vt同层的顶点(保留Vt)，并删去这些顶点相关联的弧，再删去从某层顶点指向同层顶点和低层顶点的弧，所剩余的各条弧的容量与残留网络中的容量相同，这样得到的网络就是残留网络的子网络，称为层次网络，记为G''(V'',E'')。
根据层次网络定义，层次网络中任意的一条弧<u,v>，有满足level(u)+1 == level(v)，这条弧也叫允许弧。直观的说，层次网络是建立在残留网络基础之上的一张“最短路径图”。从源点开始，在层次网络中沿着边不管怎么走，到达一个终点之后，经过的路径一定是终点在残留网络中的最短路径。
（实际操作中，只需要标记顶点层次即可，不需要执行删除操作）
阻塞流：设容量网络的一个可行流为f，当该网络的层次G''中不存在增广路(即从源点Vs到汇点Vt的路径时)，称该可行流f为层次网络G''的阻塞流。
2、最短路增广路径的算法思想
最短增广路的算法思想是：每次在层次网络中找一条含弧数最少的增广路进行增广。最短增广路算法的具体步骤如下：
（1）初始化容量网络和网络流。
（2）构造残留网络和层次网络，若汇点不在层次网络中，则算法结束。
（3）在层次网络中不断用BFS增广，直到层次网络中没有增广路为止；每次增广完毕，在层次网络中要去掉因改进流量而导致饱和的弧。
（4）转步骤（2）。
在最短增广路算法中，第（2）、（3）步被循环执行，将执行（2）、（3）步的一次循环称为一个阶段。在每个阶段中，首先根据残留网络建立层次网络，然后不断用BFS在层次网络中增广，直到出现阻塞流。注意每次增广后，在层次网络中要去掉因改进流量而饱和的弧。该阶段的增广完毕后，进入下一阶段。这样的不断重复，直到汇点不在层次网络中为止。汇点不在层次网络中意味着在残留网络中不存在一条从源点到汇点的路径，即没有增广路。
在程序实现的时候，并不需要真正“构造”层次网络，只需要对每个顶点标记层次，增广的时候，判断边是否满足level(v) = level(u)+1这一约束条件即可。
3、最短增广路算法复杂度分析
最短增广路的复杂度包括建立层次网络和寻找增广路两部分。
在最短增广路中，最多建立n个层次网络，每个层次网络用BFS一次遍历即可得到。一次BFS的复杂度为O（m），所以建层次图的总复杂度为O（n*m）。
每增广一次，层次网络中必定有一条边会被删除。层次网络中最多有m条边，所以认为最多可以增广m次。在最短增广路算法中，用BFS来增广，一次增广的复杂度为O（n+m），其中O（m）为BFS的花费，O（n）为修改流量的花费。所以在每一阶段寻找增广路的复杂度为O（m*(m+n)） = O(m*m)。因此n个阶段寻找增广路的算法总复杂度为O(n*m*m)。
两者之和为O（n*m*m）。
以上介绍最短增广路算法只是为下面介绍Dinic算法而提供给大家一个铺垫，有了以上的基础，接下来我们来介绍Dinic算法，Dinic其实是最短增广路算法的优化版。
<pre name="code" class="cpp">#include <iostream>
#include <queue>
using namespace std;
#define arraysize 201
int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //记录残留网络的容量
int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用
int pre[arraysize]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
int n,m;
queue<int> myqueue;
int BFS(int src,int des)
{
int i,j;
while(!myqueue.empty()) //队列清空
myqueue.pop();
for(i=1;i<m+1;++i)
{
pre[i]=-1;
}
pre[src]=0;
flow[src]= maxData;
myqueue.push(src);
while(!myqueue.empty())
{
int index = myqueue.front();
myqueue.pop();
if(index == des) //找到了增广路径
break;
for(i=1;i<m+1;++i)
{
if(i!=src && capacity[index][i]>0 && pre[i]==-1)
{
pre[i] = index; //记录前驱
flow[i] = min(capacity[index][i],flow[index]); //关键：迭代的找到增量
myqueue.push(i);
}
}
}
if(pre[des]==-1) //残留图中不再存在增广路径
return -1;
else
return flow[des];
}
int maxFlow(int src,int des)
{
int increasement= 0;
int sumflow = 0;
while((increasement=BFS(src,des))!=-1)
{
int k = des; //利用前驱寻找路径
while(k!=src)
{
int last = pre[k];
capacity[last][k] -= increasement; //改变正向边的容量
capacity[k][last] += increasement; //改变反向边的容量
k = last;
}
sumflow += increasement;
}
return sumflow;
}
int main()
{
int i,j;
int start,end,ci;
while(cin>>n>>m)
{
memset(capacity,0,sizeof(capacity));
memset(flow,0,sizeof(flow));
for(i=0;i<n;++i)
{
cin>>start>>end>>ci;
if(start == end) //考虑起点终点相同的情况
continue;
capacity[start][end] +=ci; //此处注意可能出现多条同一起点终点的情况
}
cout<<maxFlow(1,m)<<endl;
}
return 0;
}
预流推进算法(未填坑)
思路；
从一个直观的想法出发：先让每条边的流量和容量相同，直到遇到流量超过容量的位置再减少容量。称当前不满足流量平衡的点为溢出节点。
但是往回推不能一个一个推，不然就变为搜索了。要有一个正确的引导机制，把回推过程引导到正确的方向。由于建立了反向狐，所以正推反推机制没有区别。
用e(u)表示流入量比流出量多了多少。
高度标号机制：如果一个节点溢出了。那么它的多余流量只能流向高度标号比它低的点（水往低处流）。高度标号是动态改变的。
重标号操作：有盈余但是周围没有标号比它低的节点时，使它的标号上升到比最低的高一点。
高度函数：高度函数H（v）返回一个节点的高度，
H（s）=V
H(t)=0,
对于残量网络中每一条边（u,v), H(u)<=H(v)+1 （要求高度不能下降太快）(r(u,v)>0)
(为什么r(u,v)>0反而h（u）<h(v)?因为我们规定h（u,v）>0的时候才能进行推进操作（把一个点的盈余给到另一个点）)
两个关键操作：
（1）推进操作：
使用对象：一条边（u,v）
使用条件：e(u)>0,r(u,v)>0,h(u)=h(v)+1 (u溢出，在两者的残量网络中高度差为1)
推进量：r(u,v)与e(u)的最小值，推进同时改变r与e
Procedure Push(u,v)
x=min{r(u,v),e(u)}
Dec(r(u,v),x) Inc(r(v,u),x)
Dec(e(u),x) Inc(e(v),x)
(2)重标号操作：
适用对象：一个节点U
使用条件：节点U溢出，残量网络中周围的点不比它低
relable（U）=min{H{i}|exisit (u,v)}+1
预流初始化