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在实际的网络流应用中占据相当重要的地位。