上次写到的EK算法， 每次进行的步骤： 一次bfs找到一条增广路径+一次的增加流量。
dinic 算法最大的优化就是： 一次bfs+一个递归找增广路径（多条） + 多次的增加流量。
看见别人是这样说的，但是第三点我还没明白：
求最大流的本质，就是不停的寻找增广路径。直到找不到增广路径为止。
对于这个一般性的过程，Dinic算法的优化如下：
（1）
Dinic算法首先对图进行一次BFS，然后在BFS生成的层次图中进行多次DFS。
层次图的意思就是，只有在BFS树中深度相差1的节点才是连接的。
这就切断了原有的图中的许多不必要的连接。很牛逼！
这是需要证明的，估计证明也很复杂。
（2）
除此之外，每次DFS完后，会找到路径中容量最小的一条边。
在这条边之前的路径的容量是大于等于这条边的容量的。
那么从这条边之前的点，可能引发出别的增广路径。
比如说 S -> b -> c -> d -> T 是一条增广路径，容量最小的边是 b -> c。
可能存在一条 S -> b -> e -> f -> g -> T 这样的增广路径。
这样的话，在找到第一条增广路径后，只需要回溯到 b 点，就可以继续找下去了。
这样做的好处是，避免了找到一条路径就从头开始寻找另外一条的开销。
也就是再次从 S 寻找到 b 的开销。
这个过程看似复杂，但是代码实现起来很优雅，因为它的本质就是回溯！
（3）
在同一次 DFS 中。如果从一个点引发不出任何的增广路径，就将这个点在层次图中抹去。
/*
Program:POJ 1273 /
Dinic
Author:Comzyh
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
const int MAX=0x5fffffff;//
int tab[250][250];//邻接矩阵
int dis[250];//距源点距离,分层图
int q[2000],h,r;//BFS队列 ,首,尾
int N,M,ANS;//N:点数;M,边数
int BFS()
{
int i,j;
memset(dis,0xff,sizeof(dis));//以-1填充
dis[1]=0;
h=0;r=1;
q[1]=1;
while (h<r)
{
j=q[++h];
for (i=1;i<=N;i++)
if (dis[i]<0 && tab[j][i]>0)
{
dis[i]=dis[j]+1;
q[++r]=i;
}
}
if (dis[N]>0)
return 1;
else
return 0;//汇点的DIS小于零,表明BFS不到汇点
}
//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广
int find(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量
{
int i,a=0;
if (x==N)return low;//是汇点
for (i=1;i<=N;i++)
if (tab[x][i] >0 //联通
&& dis[i]==dis[x]+1 //是分层图的下一层
&&(a=find(i,min(low,tab[x][i]))))//能到汇点(a <> 0)
{
tab[x][i]-=a;
tab[i][x]+=a;
return a;//这个地方就是高明之处，因为增广路径会有多条，所以这条语句会多次返回，返回所有可以增加的流量
}
return 0;
}
int main()
{
int i,j,f,t,flow,tans;
while (scanf("%d%d",&M,&N)!=EOF){
memset(tab,0,sizeof(tab));
for (i=1;i<=M;i++)
{
scanf("%d%d%d",&f,&t,&flow);
tab[f][t]+=flow;
}
//
ANS=0;
while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束
{
while(tans=find(1,0x7fffffff))ANS+=tans; //一次BFS要不停地找增广路,直到找不到为止
}
printf("%d\n",ANS);
}
system("pause");
}