首先直接贴上代码（下边解释）：
View Code //----Dinic的递归实现-------- #define NOT(x) ((x&1)?(x+1):(x-1))
struct Edge
{ int u; int value; int next;
}edge[MAXM*2]; int node[MAXN];
int level[MAXN];
int queue[MAXN];
int S,T; bool build()
{ int front=0,rear=0,v,u,value; memset(level,0,sizeof(level)); level[S]=1; queue[rear]=S; while(front<=rear) { v=queue[front++]; for(int i=node[v];i!=-1;i=edge[i].next) { u=edge[i].u; value=edge[i].value; if(value && level[u]==0) { level[u]=level[v]+1; queue[++rear]=u; if(u==T) return true; } } } return false;
}
int find(int v,int beforemin)
{ int ans=0,u,value,flow; if(v==T || beforemin==0) return beforemin; for(int i=node[v];i!=-1;i=edge[i].next) { u=edge[i].u; value=edge[i].value; if(level[u]=level[v]+1 && (flow=find(u,min(beforemin,value)))) { edge[i].value-=flow; edge[NOT(i)].value+=flow; ans+=flow; beforemin-=flow; if(beforemin==0) break; } } return ans;
}
int Dinic()
{ int ans=0; while(build()) { ans+=find(S,MAX_INT); } return ans;
}因为是递归，所以搜索到的点都有自己在内存中的程序区即函数的所有变量等各自一份。
下面先说明一下一些重要变量的作用：
beforemin：表示搜索到该结点之前所有边之中的最小流量值
flow：在find函数回溯时使用，用于记录更新正反向边的流量值
ans：用于累加flow，为什么？因为是递归，为了提高效率！一般情况下，若找到一条增广路则需要从汇点到原点更新该增广路上各个边的流量值，然后再从头找！再从头找！！！如果是一个复杂的图，这样效率岂不是太低了，如果我们直接在回溯时找到更新后流量值最后一个变为0的边的头结点，（而这一点就是利用beforemin变量实现）然后继续在这个头结点上寻找其它增广路。但是这样的话，前面的结点没有回溯到，也就是前面的各边上的流量值没被更新，。这怎么办，这不是错了？额，这就是要用ans的目的，它把在该结点之前所有边每一次需要更新的流量值累加了起来！所有结点中的ans都如此，记录经过该结点的增广路的所有流量之和。还有一个问题，当在某一点的所在的函数中的ans累加后，并继续寻找时，那么它之前的边的最小流量值岂不变了？对了，就是变了，必须变，这就有用到了beforemin，更新一下beforemin的值即可！具体细节看下面例子。
下面就举一个例子：
如图：红色大写字母为结点，S为原点、T为汇点；绿色数字表示所分的级别；蓝色数字表示该边的容量（叙述中直接说成流量，它的含意就是剩余可用的流量）； 声明：大写字母的含意，eg：A表示A结点或调用A结点的find函数； 首先，ans+=find(S,MAX_INT); 进入S：beforemin=MAX_INT；ans=0；找到A结点 进入A：beforemin=3；ans=0；找到B结点 进入B：beforemin=1；ans=0；找到T结点 进入T：beforemin=1；返回1；
回到B中：flow=1；更新BT边的正反向流量值；更新beforemin的值 那么更新后beforemin（即减去flow）的值具有什么含意？更新后的beforemin就是在该结点之前的所有边的流量 （就是都已经减去flow后的流量）的最小值，以便于为继 续寻找做准备，然后ans+=flow（稍后再说这个）；最后beforemin与0比较，为什么？就是为了判断在B结点之前是否还有边（假如减去flow，也就是更新后的边）的流量为0；若为0，则break；果断返回！因为在呆在这里已毫无意义！若不为0，说明之前边若更新后还有流量，则继续在该结点下寻找。那么这个ans+=flow是怎么回事？其实这个ans用也就用在beforemin不为0时，才起到作用！当beforemin为0返回的ans，此时的ans与flow有区别？一样！当不为0时，就是把该增广路的flow记到ans上，然后继续寻找别的增广路……假设啊！我说的是假设此时在B中beforemin!=0，当然这里==0了，最后经过S->A->B的所有增广路的flow都在累加在B的ans中了，然后B函数返回，B之前的边老账新账一起算、一起更新！好了，回到程序中：这里beforemin==0成立 break；返回1；
回到A中：flow=1；更新AB边的正反流量值；更新beforemin的值； 此时beforemin!=0;（这次不用假设了，都成实事了！）好了，说明在A之前不存在一边（该边更新后为0）那么AB就是最后的一个更新后为0的边！而A就是该边的头结点呵（我自己起的呵），beforemin=2；ans=1；然后继续找找到结点C
进入C中：beforemin=1；ans=0；找到T结点 进入T中：beforemin=1；返回1；
回到C中：flow=1；更新……更新……beforemin=0，返回1； 回到A中：flow=1；更新……更新……beforemin=1，ans=2； 继续……已无路可走，返回2；
回到S中：更新……ans=2；然后走左路，最终返回给S的是0；然后走右路，最终返回给S的仍是0；（这两个过程有兴趣了，你可以自己分析分析，呵呵）最终S的find函数将返回，返回2
分析完了，你能体会到它的魅力，它的强大吗？
魅力1：find函数中使用的beforemin变量，它在所找到增广路的每一个结点上（所在的find函数中）各有一份，各有各的含义，各有各的用途，概况来说是表示在该结点之前搜索的所有边流量的最小值，那么显然在T点（汇点）中的beforemin就表示该增广路中各边中的最小流量值，我们为了提高效率去寻搜索中第一个为最小流量的边（的头结点，然后继续搜），在回溯中就要用到该变量，而S点（源点）中的beforemin为最大值，我们可以认为S之前边的最小流量无穷大，这样S点就会把所有路都搜索一遍，以找到增广路。
魅力2：find函数中使用的ans变量，它在各个结点内也各有一份，表示流过该结点的流量值和，也同样是为了辅助这一特性（为了提高效率，可能有一部分结点没回溯，以致一部分边的流量没更新！）在该结点上累加了流过该结点的流量----到回溯时，给你一起算！因为是递归，回溯是的路线一定是你走过的路线；因为是递归，你在我上边，你就欠我的迟早要还；
啊！终于写完了~从写到发表也用了好长时间，总之用心写一篇博客不容易啊！
最新评论