網路最大流演算法—Dinic演算法及優化

前置知識

網路最大流入門

前言

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<cstdio>
#include<cstring>
#include<queue>
#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;
}