Dinic算法补充

当前弧优化跟剪枝一定要一起用！

dinic算法容错高的地方在于，只要每一轮扩增的流都是一个正确的可行流，都能保证它最后输出的那个结果是对的，但是这样一来，也会使得有人写出一些时间复杂度极差的假Dinic。

在dinic算法中，我们必须要尽可能保证每一轮扩增的流都是阻塞流，否则最坏情况下，每一轮至扩增了一条增广路，那算法的时间复杂度也就退化到了朴素的EK。

当前弧优化思路

在算法Dinic中，

对于任意一条已知节点，都可使用当前弧优化

经过前面的dfs，在转化成level graph的residual graph中；

对于任意节点i，在来自上一层的入度可能不止1；

用$in[i],out[i]$分别表示节点i的入度和出度

也就是说，对于level graph的每个中间层节点，在做depth frist search时，

因为dinic中的dfs是基于level graph的特性进行的优化，

并不会像我们平时写dfs时用做标记的方法剪枝，

可能被遍历过不止一次，如果不做任何优化；

每一次遍历都从其头指针开始的的话，那么整个dfs过程中，

i节点，共被访问了$in[i]$次，每次访问的时间消耗为 $o(out[i])$量级

其总时间消耗是$o(in[i]*out[i])$

即该点的入度乘以该点的出度

然而在 $in[i]$远超常数量级时程序会明显变慢

所以既然i节点必然被访问多次，我们不妨减小每次访问带来的消耗

当前弧优化指的是在访问i并以i作为新的dfs起点时，

可以从上一次访问过的地方开始遍历其邻接边，

那上一次访问过的地方我们就用$cur[i]$记录

所以在没有访问过的时候有$cur[i]=head[i]$

并且在每一次访问它的下一个邻接点时对$cir[i]$进行更新

这样一来保证了在每次dfs中，该节点的每个邻接点只被访问过一次，

总的时间消耗就由原先的$o(in[i]*out[i])$降低至$o(in[i]+out[i])$

$in[i]$为访问到i节点这个行为本身所带来的时间消耗

所以这样一来，在i节点上的时间成本一下子就变成线性的了；

紧接着问题就变成了，为什么上一次访问会剩下节点，这样做又为什么会是对的

根据上面讲的我们发现，当前弧优化的合理性依赖于两个条件：

• 上一次遍历完之后还剩下一些节点让我们能够接着上次的继续遍历
• 在经过当前弧优化后每次dfs还能找到阻塞流

如果不剩的话会出现的情况是这样的：

当节点i第一次被访问到时就一次性遍历完了它的所有出度，$cur[i]$也直接更新为邻接的最后一个点，拿还去维护一个这样的数组还有什么意义，直接用最传统的标记法剪枝好像是一样的效果。

所以说当前弧优化会结合另一种剪枝方法使用，这种感觉有点像线段树里的lazytag，具体实现原理是这样的：

在以节点i作为新起点的dfs中，如果在遍历到某条邻接边返回后发现，当前节点已经没有剩余流量，也就是说在当前的residual graph中（只看包含i的所有分支），如果不利用反向边进行"撤销"操作，该部分的流量已经无法继续增大 了（此时称这个流为阻塞流，注意阻塞流不一定是最大流），这样一来，后面的那些邻接边其实走不走都一样。所以我们在当前节点流量用完时，就及时跳出将剩下的边留给后面来的结点继续用，这样既降低了当前轮的时间消耗，也保证了剩余的边不被浪费

rest-=nowflow;
            if (rest==0) break;

注意：如果这个时候还执意走了这些边，将达不到优化算法的效果，因为如果剩下的边没有被后面来的节点访问到，那么相当于被直接浪费掉，这样会导致每次dfs扩增时形成的流不再是阻塞流，从而间接增加了Dinic算法循环的轮次数！

附dinic代码

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN=(2e+2)+20,MAXM=(1e+4)+20;
const long long INF=9223372036854775807;
struct Edge{
    int to,nex;
    long long c;
}edges[MAXM];
int n,m,s,t,u,v,tot=1,head[MAXN],depth[MAXN],cur[MAXN];
long long w,nowflow,ans;
inline void addedge(int x,int y,int val){
    ++tot;edges[tot].c=val;edges[tot].nex=head[x];
    edges[tot].to=y;head[x]=tot;
}
inline bool bfs(){
    memset(depth,0,sizeof(depth));
    queue<int>o;
    o.push(s);depth[s]=1;
    cur[s]=head[s];
    while (!o.empty()){
        int now=o.front();
        o.pop();
        for (int i=head[now];i;i=edges[i].nex){
            int x=edges[i].to;
            cur[x]=head[x];
            if (depth[x]==0&&edges[i].c>0){
                o.push(x);
                depth[x]=depth[now]+1;
                if (x==t) return true;
            }
        }
    }
    return false;
}
inline long long dfs(int now,long long nowC=INF){
    if (now==t) return nowC;
    long long sum=0,rest=nowC;
    for (int i=cur[now];i;i=edges[i].nex){
        cur[now]=i;
        int x=edges[i].to;
        if (depth[x]==depth[now]+1&&edges[i].c>0){
            nowflow=dfs(x,min(rest,edges[i].c));
            edges[i^1].c+=nowflow;
            sum+=nowflow;
            edges[i].c-=nowflow; 
            rest-=nowflow;
            if (rest==0) break;
        }
    }
    if (sum==0) depth[now]=0;
    return sum;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int i=1;i<=m;i++){
        scanf("%d%d%lld",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,0);
    }
    while (bfs()) ans+=dfs(s);
    printf("%lld",ans);
    return 0;
}