Dinic算法介绍

一、概述

Dinic算法是最大流算法中的一种，其时间复杂度为O(n²m)，但是有更好的最坏时间复杂度O(nm*log(U))，与Hopcroft−Karp的O(m²√n)相比，在密集图或者容量较大时，Dinic算法对于求解最大流有更好的表现，适用性更广。

二、原理

Dinic算法的基本思路是：通过多次增广，每次增加的流量不低于上一次增加的流量，直至无法增广为止，这样求得的就是最大流量。具体思路如下：

首先设置dfs流程，使其能够和BFS流程相对应，dfs的返回值代表可以从当前节点流入汇点的最大流量，如果当前节点等于源点就返回无穷大（因为一开始源点的可行流量等于无穷）。
其次，设置BFS流程，使其在调用dfs时可以从当前节点到达汇点（即dist[t]≠-1），并返回增加的流量，如果增加的流量为0或者小于0，则直接break（即优化掉死路）。
最后通过不停地调用BFS和DFS，每次维护一组残量图，直到不存在增广路为止。整个过程中，每次增广的流量都会不小于上一次的增加量，因此需要满足连续增广，并且BFS成功与否决定了DFS会返回多大的可行流量。

三、应用

Dinic算法的应用主要在网络流中，可以求一个图中所有源点到汇点的最大流量（源点可能有多个），并且对于同一对源点-汇点，最多可以同时执行一次Dinic算法。代码示例：

typedef int type; // 容量，类型名称视情况更改
struct edge
{
    int to, rev;
    type cap;
};
vector<edge> 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<int> q;
    level[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        for(int i = 0; i < G[v].size(); i++)
        {
            edge &e = G[v][i];
            if(e.cap > 0 && 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]; i < G[v].size(); i++)
    {
        edge &e = G[v][i];
        if(e.cap > 0 && level[v] < level[e.to])
        {
            type d = dfs(e.to, t, min(f, e.cap));
            if(d > 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) return flow;
        memset(iter, 0, sizeof(iter));
        type f;
        while((f = dfs(s, t, INF)) > 0)
        {
            flow += f;
        }
    }
}

四、优化

Dinic算法的常见优化方法有：

分层图（Level Graph）：最宽松的限制即每层只存储一次。即当前队列中存在两个点属于同一层，除非在更新某个点的距离后重新进行BFS，否则不会再向某层的点增加新的点。
在BFS时记录一组“pointer”：用于在DFS过程中从上次的返回点继续搜索，而不是从起点开始搜索。这种操作虽然为线性，但是其作用显然不及第一种优化（实际上第一种优化存在时间复杂度为O(n²m)的情况）。
使用最大流速度和一般的带宽不同：所以可以频繁地调整容量或者调整浮点数。最好还是针对不同的网络设置最适当的流媒体参数。
减弱其“最坏时间复杂度比某些算法还不如”的不足之一：采用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<int> 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在实际的网络流应用中占据相当重要的地位。