最大流-Dinic算法,原理详解,四大优化,详细代码

发布时间:2024年01月23日

零、前言

关于网络流、最大流基本概念见:最大流—EK算法,流网络,残留网络,定理证明,详细代码-CSDN博客


一、概念回顾(可略过)

已经在最大流—EK算法,流网络,残留网络,定理证明,详细代码-CSDN博客中介绍过

1.1流网络

流网络G = (V , E)是一个有向图,其中每条边(u , v)∈E均有一非负容量c(u , v) ≥ 0。如果(u , v) ? E,则c(u , v) = 0。

流网络中有两个特别的点:源点s汇点t如例中的工厂和仓库。

1.2流

设f(x , y)是定义在节点二元组(x∈V , y∈V)上的实数函数,且满足:

  1. 容量限制 : f ( x , y ) ≤ c ( x , y ) 容量限制:f(x , y) \le c(x , y) 容量限制:f(x,y)c(x,y)

  2. 反对称性 : f ( x , y ) = ? f ( y , x ) 反对称性:f(x , y) = -f(y , x) 反对称性:f(x,y)=?f(y,x)

  3. 流守恒性 : ? x ≠ s , x ≠ t , ∑ ( u , x ) ∈ E f ( u , x ) = ∑ ( x , v ) ∈ E f ( x , v ) 流守恒性:\forall x \ne s,x \ne t,\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v) 流守恒性:?x=s,x=t,(u,x)E?f(u,x)=(x,v)E?f(x,v)

f(x,y)称为流网络的流函数 , 对于(x , y)∈E , f(x , y)称为边的流量 , c(x , y) - f(x , y)称为边的剩余流量.

流 f 值的定义为
∣ f ∣ = ∑ v ∈ V f ( s , v ) \left |f \right | = \sum_{v\in V}f(s,v) f=vV?f(s,v)
亦即 , 从源点s发出的总流。如例中每天从工厂发出的冰球的箱数。

1.3最大流

对于一个给定的流网络 , 合法的流函数 f 有很多. 使得流的值最大的流函数被称为网络的最大流 , 此时的流的值被称为网络的最大流量.

1.4残留网络

假定有一个流网络G = (V , E),其源点为s,汇点为t。设f为G中的一个流,一对顶点u, v∈V。在不超过容量c(u,v)的条件下从u到v之间可以压入的额外网络流量,就是**(u,v) 的残留容量(residual capacity)**,由下式定义:
c f ( u , v ) = c ( u , v ) ? f ( u , v ) c_{f}(u,v) = c(u,v) - f(u,v) cf?(u,v)=c(u,v)?f(u,v)

给定一流网络G = (V , E)和流f,由f压得的G的残留网络是Gf = (V , Ef),其中:
E f = { ( u , v ) ∈ V × V : c f ( u , v ) > 0 } E_{f} = \{ (u,v)\in V\times V:c_{f}(u,v)>0 \} Ef?={(u,v)V×V:cf?(u,v)>0}
即,残留网络包含了流网络的所有点,和残留容量大于0的有向边。

注意Ef中的边既可以是E中的有向边也可以是其反向边,若(u , v)∈E,有f(u , v) < c(u , v),那么根据流网络的性质可知f(v , u) = -f(u,v),那么对应残留容量就是c(v , u) - (-f(u,v)) = c(v , u) + f(u , v) > 0,则其反向边也在残留网络中。

由残留网络可以得出引理

f 为G中的一个流,f‘为Gf中的一个流,那么f + f’仍为流网络G的一个流,其流量为| f + f’ | = | f | + | f‘ |

具体证明可以自己尝试或见《算法导论》

1.5增广路径

已知流网络G = (V , E)和流f,增广路径p残留网络Gf中由源点s到汇点t的一条简单路径

根据残留网络的定义,增广路径上的每条边的剩余容量都大于0,则该路径上的每条边都可以额外容纳一定的流量,这也和我们后续求最大流密切相关。

不难想出,增广路径可以增加的最大流量为该路径上边的最小残留容量

1.6流网络的割

流网络G = (V , E)的割(S , T)将V划分为S和T两部分,使得s∈S,t属于T,通过割的流量为S和T之间边上流量的代数和,但是割的容量仅包含从S到T的边的容量的代数和

如下图,割(S,T)的流量f(S,T) = 12 - 4 + 11 = 19

容量c(S,T) = 12 + 14 = 26

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

我们称容量最小的割为最小割

可以证明f(S , T) = | f | ≤ c(S, T)(证明见《算法导论》)

1.7最大流最小割定理

如果 f是具有源点s和汇点t的流网络G = (V , E)中的一个流,那么下列条件是等价的:

  1. f是G的一个最大流
  2. 残留网络Gf不包含增广路
  3. 存在G的某个割(S , T),有| f | = c(S , T)
1.7.1证明

采用循环证明法,(1) => (2) , (2) => (3) , (3) => (1)

(1) => (2):

很容易证明,采用反证法即可

假设Gf含增广路,那么我们可以在Gf中构造一流f’,| f‘ | = min(cf(u,v) , (u , v) ∈ Ef),那么f + f’仍为流网络的一个流(由1.4中介绍的引理可知),那么|f + f‘| > | f |,那么f就不是最大流,矛盾,则(1) => (2)成立

(2) => (1):

我们只需要在(2)的条件下构造出一个满足(3)的割即可。

选取集合S = {v ∈ V:Gf中从s到v存在一条通路},T = V - S,划分(S , T)为一个割。

对所有<u , v>,u∈S,v∈T,f(u , v) = c(u , v),否则v就属于S。

由此推出| f | = f(S , T) = c(S , T)

(3) => (1):

也很容易证明,由于由于| f | ≤ c(S, T),而此时| f | = c(S , T),故不存在比f更大的流,故f为最大流。

1.8Ford-Fulkerson方法

Ford-Fulkerson方法是最大流的经典求解方法,之所以称之为”方法“而非”算法“,是由于它包含具有不同运行时间的几种实现。

Ford-Fulkerson方法依赖于三种重要思想:残留网络(residual network)、增广路(augmenting path)和割(cut)。这些思想是最大流最小割定理的精髓,这里给出Ford-Fulkerson方法的特定实现。

伪代码如下:

Ford-Fulkerson(G , s , t)
初始化流f = 0
while 流网络中存在增广路p
	do 沿着p增加f
return f

二、Dinic算法

2.1EK算法的可优化之处

Dinic算法其实就是对于EK算法的优化。

无论是Dinic算法还是EK算法它们都是基于FF方法来求最大流,我们回看EK算法的实现原理:

  • bfs找到一条增广路
  • 更新增广路上边的剩余容量
  • 找不到增广路,算法结束,时间复杂度O(n^2 m)

很明显,EK算法有个问题就是每次只找一条增广路然后进行更新,然后再从源点开始找增广路,我们有如下疑问:

  • 我们能否一次更新多条增广路的剩余容量呢?
  • 对于网络中的多条增广路,我们如何尽可能快的找到增广路呢?

2.2Dinic算法的优化策略

  1. 搜索顺序优化:根据每个点到源点距离,建立分层图,bfs一层一层地去增广,对于不在当前bfs层的下一层的点不进行进一步搜索,避免往回来回走,降低效率
  2. 当前弧优化:dfs更新多条增广路容量时,对于每个顶点发出的边,其所在增广路已经更新过的边进行剪枝
  3. 剩余容量优化:很容易理解,能够增加的流量用完了,就剪枝
  4. 残枝优化:如果该点不在增广路上就剪枝

1是在bfs中的优化,比较直观,2、3、4是在dfs更新容量中的优化,可以结合后续代码理解

2.3Dinic算法原理

2.3.1找增广路

仍然是bfs往下搜索,直到遇到汇点t,只不过我们枚举每个点u时,将其未访问过的邻接点v的深度d[v]设置为d[u] + 1,即一层一层往下找,后面更新也是一层一层往下更新回溯

2.3.2更新剩余容量

EK算法更新剩余容量的策略是记录增广路上节点的前驱节点,从汇点往前一个一个更新

我们Dinic算法更为高效,对一个点发出去的多条增广路上的点都进行更新,对于要更新的点给其一个容量限制limit,即最多能增加的流量,对于每个邻接点v对其深搜,给v的limit为min(limit , w(u,v)),然后获取深搜v得到的v发出的所有增广路能够增加的流量和incf,对边(u,v)的剩余容量进行更新,当然limit也要相应减少

可见dinic是通过深搜加回溯完成了多条增广路的剩余容量更新。

2.4算法流程

  • dinic算法不断重复以下步骤,直到在残留网络中无法到达t
    • bfs建立分层图的同时找增广路
    • dfs从源点开始遍历增广路,回溯时更新剩余容量,初始给源点s的可增加流量上限limit为inf(无穷大)
  • 时间复杂度O(nm^2),实际中远达不到这个上界,可以解决1e4量级的数据

2.5代码实现

#define int long long
#define N 205
#define M 5005
const int MOD = 10000007;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m, s, t, idx;
int d[N], cur[N], head[N]; // 深度,当前边,前向星头

struct edge
{
    int v, c, nxt;
} edges[M << 1];

inline void addedge(int u, int v, int c)
{
    edges[idx] = {v, c, head[u]};
    head[u] = idx++;
}

bool bfs() // 多路增广,分层搜索优化
{
    memset(d, 0, sizeof(d));
    queue<int> q;
    q.emplace(s), d[s] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edges[i].nxt)
        {
            int v = edges[i].v;
            if (!d[v] && edges[i].c)
            {
                d[v] = d[u] + 1;
                q.emplace(v);
                if (v == t)
                    return true;
            }
        }
    }
    return false;
}

int dfs(int u, int limit)
{
    if (u == t)
        return limit;
    int ret = 0;
    for (int i = cur[u]; ~i && limit > 0 ; i = edges[i].nxt)//limit > 0 余量优化
    {
        cur[u] = i;// 当前弧优化
        int v = edges[i].v;
        if (d[v] == d[u] + 1 && edges[i].c)
        {
            int incf = dfs(v, min(limit, edges[i].c));
            if (!incf)
                d[v] = 0; //剪枝优化
            edges[i].c -= incf, edges[i ^ 1].c += incf, ret += incf, limit -= incf;
        }
    }
    return ret;
}

int dinic()
{
    int ret = 0;
    while (bfs())
        memcpy(cur, head, sizeof(head)), ret += dfs(s, inf);

    return ret;
}

2.6OJ模板练习

P3376 【模板】网络最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

直接跑板子即可,这道题数据量过小,EK算法也能过

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_set>
#include <map>
#include <bitset>
using namespace std;
#define sc scanf
#define int long long
#define N 205
#define M 5005
const int MOD = 10000007;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m, s, t, idx;
int d[N], cur[N], head[N]; // 深度,当前边,前向星头

struct edge
{
    int v, c, nxt;
} edges[M << 1];

inline void addedge(int u, int v, int c)
{
    edges[idx] = {v, c, head[u]};
    head[u] = idx++;
}

bool bfs() // 多路增广,分层搜索优化
{
    memset(d, 0, sizeof(d));
    queue<int> q;
    q.emplace(s), d[s] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edges[i].nxt)
        {
            int v = edges[i].v;
            if (!d[v] && edges[i].c)
            {
                d[v] = d[u] + 1;
                q.emplace(v);
                if (v == t)
                    return true;
            }
        }
    }
    return false;
}

int dfs(int u, int limit)
{
    if (u == t)
        return limit;
    int ret = 0;
    for (int i = cur[u]; ~i && limit > 0 ; i = edges[i].nxt)//limit > 0 余量优化
    {
        cur[u] = i;// 当前弧优化
        int v = edges[i].v;
        if (d[v] == d[u] + 1 && edges[i].c)
        {
            int incf = dfs(v, min(limit, edges[i].c));
            if (!incf)
                d[v] = 0; //剪枝优化
            edges[i].c -= incf, edges[i ^ 1].c += incf, ret += incf, limit -= incf;
        }
    }
    return ret;
}

int dinic()
{
    int ret = 0;
    while (bfs())
        memcpy(cur, head, sizeof(head)), ret += dfs(s, inf);

    return ret;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("in.txt", "r", stdin);
    cin >> n >> m >> s >> t;
    int a, b, c;
    memset(head, -1, sizeof(head));
    for (int i = 0; i < m; i++)
        cin >> a >> b >> c, addedge(a, b, c), addedge(b, a, 0);
    cout << dinic();
}

文章来源:https://blog.csdn.net/EQUINOX1/article/details/135793883
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。