前置知识

前言

Dinic在信息学奥赛中是一种最常用的求网络最大流的算法。

它凭借着思路直观，代码难度小，性能优越等优势，深受广大oier青睐

思想

$Dinic$算法属于增广路算法。

它的核心思想是：对于每一个点，对其所连的边进行增广，在增广的时候，每次增广“极大流”

这里有别于EK算法，EK算法是从边入手，而Dinic算法是从点入手

在增广的时候，对于一个点连出去的边都尝试进行增广，即多路增广

 

Dinic算法还引入了分层图这一概念，即对于$i$号节点，用$dis(i)$表示它到源点的距离，并规定，一条边能够被增广，当且仅当它连接的两个点$u,v$满足：$dis(v)=dis(u)+1$，这样可以大大优化其时间复杂度。

 

实现

有了上面的知识，Dinic实现起来也就比较简单了。

每次BFS构造分层图（注意必须每次都重新构造，因为每次增广之后会删除一些无用的边，也就会删除一些无用的点）

然后从源点开始多路增广

 

优化

• 当前弧优化：对于每个点，我们记录下它已经增广了哪些边，当再次回到这个点的时候，无视已经增广过的边，从下一条边开始增广
• 分层优化（自己xjb起的名字）：在进行分层的时候，找到汇点立即退出
• 剩余量优化（也是自己起的）：在进行增广的时候，如果该节点已经没有流量，直接退出

时间复杂度

Dinic算法的理论时间复杂度为$O(n^2*m)$

证明可以看

但是！

Dinic算法的性能在比赛中表现的非常优越。

按照集训队大佬ly的说法，我们可以认为Dinic算法的时间复杂度是线性的（比某标号算法不知道高到哪里去了）

代码

#include
     
      #include
      
       #include
       
        #define AddEdge(x,y,z) add_edge(x,y,z),add_edge(y,x,0);using namespace std;const int MAXN=1e6+1;const int INF=1e8+10;inline char nc(){    static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){    char c=nc();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=nc();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}    return x*f;}int N,M,S,T;struct node{    int v,flow,nxt;}edge[MAXN*4];int head[MAXN],cur[MAXN],num=0;//注意这里必须从0开始 inline void add_edge(int x,int y,int z){    edge[num].v=y;    edge[num].flow=z;    edge[num].nxt=head[x];    head[x]=num++;}int deep[MAXN],q[MAXN];inline bool BFS(){    memset(deep,0,sizeof(deep));    deep[S]=1;    int l=0,r=1;    q[++l]=S;    while(l<=r)    {        int p=q[l++];        for(int i=head[p];i!=-1;i=edge[i].nxt)            if(!deep[edge[i].v]&&edge[i].flow)            {                deep[edge[i].v]=deep[p]+1;q[++r]=edge[i].v;                if(edge[i].v==T) return 1;//当找到汇点的时候直接返回 快30ms             }    }    return deep[T];}int DFS(int now,int nowflow){    if(now==T)    return nowflow;    int totflow=0;//从这个点总共可以增广多少流量     for(int i=head[now];i!=-1;i=edge[i].nxt)//当前弧优化 快150ms     {        if(deep[edge[i].v]==deep[now]+1&&edge[i].flow)//只有满足距离要求与流量要求的点才能进行增广         {            int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));            edge[i].flow-=canflow;edge[i^1].flow+=canflow;//增广             totflow+=canflow;            nowflow-=canflow;            if(nowflow<=0) break; //当前点已经没有流量  快100ms         }    }    return totflow;}void Dinic(){    int ans=0;    while(BFS())//每次构造分层图     {        memcpy(cur,head,sizeof(head)); //当前弧优化         ans+=DFS(S,INF);//进行增广     }    printf("%d",ans);}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    N=read();M=read();S=read();T=read();    memset(head,-1,sizeof(head));    for(int i=1;i<=M;i++)    {        int x,y,z;        x=read();y=read();z=read();        AddEdge(x,y,z);    }    Dinic();    return  0;}