// 此博文为迁移而来，写于2015年2月6日，不代表本人现在的观点与看法。原始地址：http://blog.sina.com.cn/s/blog_6022c4720102vrg4.html
今天我们来谈谈网络流之Dinic算法。这种算法相比Edmond-Karp算法，更加快速，更加常用。还记得EK吗？每次为了防止流量堵塞，必须进行多次BFS/DFS，非常费时间。而Dinic大叔非常机智的发明了Dinic算法，让这个问题得以解决。
Dinic的核心内容是：反复进行BFS绘制出层次图，和DFS进行增广。所谓的层次图就是什么呢？ 从源点到当前点的最近距离，可以存储到一个数组dep中。如图所示，这张图上，dep[1]=0，dep[2]=2，dep[3]=2，dep[4]=1。
而层次图有什么用呢？1、在DFS增广时，当且仅当下一个点的层次是当前点的下一层才进入下一个点；2、是用来判断源点到汇点是否还有流量可以流。如果汇点已经不再层次图上了，说明没有多余的流量可以从源点流到汇点了，这个时候就可以结束搜索而输出答案了。
那么每进行完一次BFS，dep数组要清空。接下来的步骤就和EK算法一个意思了，但是正如*所说，这个是需要设置反向弧使流量可以顺利流走。找出当前增广路的最小流量，到汇点后将本增广路的所有子路减去该流量，且所有反向弧增加该流量。如图所示：
// 原图已经丢失，无法进行迁移
代码如下：
#include<cstdio>
#include<cstring>
#define MAXN 205
#define MAXM 205
#define INF 1<<30
struct edge
{
int v,next,flow;
};
int dep[MAXN],s,t,ans,h[MAXN],u,v,flow,m,n,tot;
edge list[MAXM];
int min(int a,int b)
{
return (a<b)?a:b;
}
void AddList(int u,int v,int flow)
{
tot++;
list[tot].next=h[u];
list[tot].v=v;
list[tot].flow=flow;
h[u]=tot;
}
void init()
{
freopen("EXMaxFlow.in","r",stdin);
freopen("EXMaxFlow.out","w",stdout);
scanf("%d %d",&m,&n);
for (int i=1;i<=m;i++)
{
scanf("%d %d %d",&u,&v,&flow);
AddList(u,v,flow);
AddList(v,u,0);
}
s=1; t=n;
}
int BFS()
{
int q[MAXN*MAXN],head,tail;
head=1; tail=2; q[1]=s; dep[s]=1;
while (head!=tail)
{
for (int x=h[q[head]];x!=0;x=list[x].next)
{
if (dep[list[x].v]==0 && list[x].flow>0)
{
dep[list[x].v]=dep[q[head]]+1;
q[tail++]=list[x].v;
}
}
head++;
}
if (dep[t]==0) return 0;
else return 1;
}
int DFS(int now,int RouteMinFlow)
{
int OldRouteMinFlow=0;
if (RouteMinFlow<=0 || now==t) return RouteMinFlow;
for (int x=h[now];x!=0;x=list[x].next)
{
if (dep[list[x].v]==dep[now]+1)
{
int temp=DFS(list[x].v,min(RouteMinFlow,list[x].flow));
list[x+1].flow+=temp;
list[x].flow-=temp;
RouteMinFlow-=temp;
OldRouteMinFlow+=temp;
if (RouteMinFlow==0) break;
}
}
return OldRouteMinFlow;
}
int main()
{
init();
while (BFS()==1) { ans+=DFS(s,INF); memset(dep,0,sizeof(dep)); }
printf("%d",ans);
return 0;
}