Dinic 模板詳解

一、概述

Dinic演算法是最大流演算法中的一種，其時間複雜度為O(n^2*m)，但是有更好的最壞時間複雜度O(nm*log(U))，與Hopcroft−Karp的O(m^2*n^0.5)相比，在密集圖或者容量較大時，Dinic演算法對於求解最大流有更好的表現，適用性更廣。

二、原理

Dinic演算法的基本思路是：通過多次增廣，每次增加的流量不低於上一次增加的流量，直至無法增廣為止，這樣求得的就是最大流量。

具體思路如下：

1.首先設置dfs流程，使其能夠和BFS流程相對應，dfs的返回值代表可以從當前節點流入匯點的最大流量，如果當前節點等於源點就返回無窮大（因為一開始源點的可行流量等於無窮）

2.其次，設置BFS流程，使其在調用dfs時可以從當前節點到達匯點（即dist[t]!=-1），並返回增加的流量，如果增加的流量為0或者小於0，則直接break（即優化掉死路）

3.最後通過不停的調用BFS和DFS，每次維護一組殘量圖，直到不存在增廣路為止。整個過程中，每次增廣的流量都會不小於上一次的增加量，因此需要滿足連續增廣，並且BFS成功與否決定了DFS會返回多大的可行流量。

三、應用

Dinic演算法的應用主要在網路流中，可以求一個圖中所有源點到匯點的最大流量（源點可能有多個），並且對於同一對源點-匯點，最多可以同時執行一次Dinic演算法。

代碼示例：

typedef int type; // 容量，類型名稱視情況更改

struct edge
{
    int to,rev;
    type cap;
};

vector G[MAXV];
int iter[MAXV],level[MAXV];

void add_edge(int from,int to,type cap)
{
    G[from].push_back((edge){to,(int)G[to].size(),cap});
    G[to].push_back((edge){from,(int)G[from].size()-1,0});
}

void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue q;
    level[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0;i0&&level[e.to]<0)
            {
                level[e.to]=level[v]+1;
                q.push(e.to);
            }
        }
    }
}

type dfs(int v,int t,type f)
{
    if(v==t)return f;
    for(int &i=iter[v];i0&&level[v]0)
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

type max_flow(int s,int t)
{
    type flow=0;
    for(;;)
    {
        bfs(s);
        if(level[t]0)
        {
            flow+=f;
        }
    }
}

四、優化

Dinic演算法的常見優化方法有：

1.分層圖（Level Graph）：最寬鬆的限制即每層只存儲一次。即當前隊列中存在兩個點屬於同一層，除非在更新某個點的距離後重新進行BFS，否則不會再向某層的點增加新的點。

2.在BFS時記錄一組「pointer」，用於在DFS過程中從上次的返回點繼續搜索，而不是從起點開始搜索。這種操作雖然為線性，但是其作用顯然不及第一種優化（實際上第一種優化存在時間複雜度為O(n^2*m)的情況）。

3.使用最大流速度和一般的帶寬不同，所以可以頻繁的調整容量或者調整浮點數。最好還是針對不同的網路設置最適當的流媒體參數。

4.減弱其「最壞時間複雜度比某些演算法還不如」的不足之一：採用HLPP演算法

代碼示例：

struct node
{
    int v,f,nx;
}p[MAXM];

int head[MAXN],cur[MAXN],d[MAXN],cnt,n,m,S,T;

inline void add_edge(int u,int v,int f)
{
    p[++cnt]=(node){v,f,head[u]};
    head[u]=cnt;
    p[++cnt]=(node){u,0,head[v]};
    head[v]=cnt;
}

inline bool bfs()
{
    for(re int i=S;i<=T;++i)
        d[i]=-1,cur[i]=head[i];
    queue q;
    d[S]=0;
    q.push(S);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=p[i].nx)
        {
            int v=p[i].v,f=p[i].f;
            if(d[v]==-1&&f)
            {
                q.push(v);
                d[v]=d[u]+1;
                if(v==T)
                    return 1;
            }
        }
    }
    return 0;
}

inline int dfs(int u,int flow)
{
    if(u==T)
        return flow;
    int ret=flow;
    for(int i=cur[u];i&&ret;i=p[i].nx)
    {
        cur[u]=i;
        int v=p[i].v,f=p[i].f;
        if(d[v]==d[u]+1&&f)
        {
            int w=dfs(v,min(ret,f));
            p[i].f-=w;
            p[i^1].f+=w;
            ret-=w;
            if(!ret)
                break;
        }
    }
    if(ret==flow)
        d[u]=-2;
    return flow-ret;
}

inline int dinic()
{
    int ans=0;
    while(bfs())
        ans+=dfs(S,0x3f3f3f3f);
    return ans;
}

五、總結

Dinic演算法作為最大流演算法的一種，能夠在較優的時間內獲得最大網路流，應用廣泛。

在實戰中，Dinic演算法的時間複雜度也更有優勢，而且最壞時間複雜度相對更小。Dinic在實際的網路流應用中佔據相當重要的地位。