网络流 – 最大流

网络流简介

容量网络

网络:指一个有向图 $G(V,E)$.

容量:在 $G$ 中,称每条边 $(u, v)$ 的权值 $c(u, v)$,为这条边的容量;特殊的,若 $(u,v)\notin E$,$c(u, v)=0$.

源点和汇点:$V$ 中的两个特殊点。一般记 $s$ 为源点,$t$ 为汇点,$s\neq t$.

流函数

网络 $G$ 的流函数是定义在二元组( $u\in V, v\in V$ )上的实数函数 $f(u, v)$.

$$
f(u,v)=
\left\{
\begin{aligned}
&f(u,v),&(u,v)\in E\\
&-f(v,u),&(v,u)\in E\\
&0,&(u,v)\notin E,(v,u)\notin E
\end{aligned}
\right.
$$

定义

对于 $(u, v)\in E$,$f(u, v)$ 称为边的流量,$c(u, v)-f(u, v)$ 称为边的剩余流量

整个网络的流量为 $\sum_{(s, v)\in E} f(s, v)$,也就是从源点出发的所有流量的和

性质

$f(u, v)$ 满足以下三条性质:

  1. 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即 $f(u,v)\leq c(u,v)$;
  2. 斜对称性:每条边的流量与其相反边的流量之和为 $0$,即 $f(u,v)=-f(v,u)$;
  3. 流守恒性:从源点流出的流量等于汇点流入的流量,即 $\forall x\in V\setminus\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$.

最大流

概述

在一个流量网络中,求从源点 $s$ 流向汇点 $t$ 的最大流量。流量定义为:从源点出发的所有流量的和

Ford-Fulkerson 增广路算法

通过寻找增广路来更新最大流。注意:这里的增广路与二分图中的增广路定义不同。

残量网络

残量:给定容量网络 $G(V, E)$ 及可行流 $f$,$(u, v)$ 上的残量记为 $c_f(u, v)=c(u, v)-f(u, v)$.

对于每条边而言,残量为这条边可以增加的容量。

残量网络:对于容量网络 $G(V, E)$ 及其上的网络流 $f$,$G$ 关于 $f$ 的残量网络为 $G_f(V_f, E_f)$. $(u, v)\in E_f$ 的边权记为 $c_f(u, v)$ . 残量网络 $G_f$ 满足:

  • $V_f=V$
  • 对于任意 $(u, v)\in E$,如果 $f(u, v) < c(u, v)$,那么 $(u, v)\in E_f$ 且 $c_f(u, v) = c(u, v) – f(u, v)$.
  • 对于任意 $(u, v)\in E$,如果 $f(u, v) > 0 $,那么 $(v, u)\in E_f$ 且 $c_f(v, u)=f(u, v)$.

通俗的来说,比如对于一条边 $(u, v)$,$f(u, v)=3$,$c(u, v)=5$。这条边的流量最多可以再增加 $2$,所以残量网络中 $c_f(u, v)=2$;同时,这条边的流量最多可以减少 $3$,又因为 $v$ 向 $u$ 增加流量,等价于 $u$ 向 $v$ 减少流量,所以在残量网路中的体现就是 $c_f(v, u)=3$。

因此,残量大于 $0$ 的边有可能不在原图 $G$ 中(但这条边的反向边在原图 $G$ 中)。

增广路

在原图 $G$ 中,若一条从源点到汇点的路径满足:路径上所有边的剩余容量都大于 $0$,那么这条路被称为增广路。

或者说,在残量网络 $G_f$ 中,能找到的从源点到汇点的路径,都是增广路。

EK算法——Edmond-Karp动能算法

思想

BFS在残量网络上找增广路,只要能找到一条增广路,就一定能对其进行增广

方法

比如我们在残量网络找到了一条路径,计算出路径上所有边中的最小剩余流量 $rest$,将所有边的剩余流量减去 $rest$ 显然满足条件,于是流量增加了。

时间复杂度为 $\mathcal{O}(nm^2)$,$n$ 为点数,$m$ 为边数。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200;
const int MAX_M = 400;
const int INF = 0x3f3f3f3f;
struct edge {
    int u, v, c, next;
} edge[MAX_M];
int head[MAX_N], eid, S, T;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int c) {
    edge[eid].u = u;
    edge[eid].v = v;
    edge[eid].c = c;
    edge[eid].next = head[u];
    head[u] = eid++;
}
void addedge(int u, int v, int c) {
    insert(u, v, c);
    insert(v, u, 0);
}
int pre[MAX_N]; // pre[u]记录节点u通过哪条边到达,记录的是边的下标
void bfs() {
    queue<int> q;
    q.push(S);
    memset(pre, -1, sizeof(pre));
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].v;
            if(pre[v] == -1 && edge[i].c) {
                pre[v] = i;
                if(v == T) {
                    break;
                }
                q.push(v);
            }
        }
        if(pre[T] != -1) {
            break;
        }

    }
}
int EK() {
    int ret = 0;
    while(1) {
        bfs();
        if(pre[T] == -1) {
            break;
        }
        int Min = INF;
        for(int u = T; u != S; u = edge[pre[u]].u) {
            Min = min(Min, edge[pre[u]].c);
        }
        for(int u = T; u != S; u = edge[pre[u]].u) {
            edge[pre[u]].c -= Min;
            edge[pre[u] ^ 1].c += Min;
        }
        ret += Min;
    }
    return ret;
}
int main() {
    int n, m;
    init();
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v, flow;
        cin >> u >> v >> flow;
        addedge(u, v, flow);
    }
    cin >> S >> T;
    cout << EK() << endl;
    return 0;
}

Dinic算法

思想

建立层次网络。对图上的点进行分级,以距离源点的最近距离的大小关系作为等级(等级从小到大,等价于距离源点的距离按升序排序)。增广的时候流量只会从低级节点走向高级节点,不会像EK算法一样出现往回走的情况。

建图方法:从源点开始BFS一遍即可。

建图之后,通过DFS找增广路。每次找增广路时的方法是多路增广。多路增广是说:每次找到一条增广路的时候,我们可以用残余的部分流量,再找出一条增广路。这样有一些边就可以少被经过一次,能够提高算法效率。

每次DFS之后再重新BFS一遍,直到图中没有增广路存在,也就是汇点不再在层次网络当中。

算法极限时间复杂度是 $\mathcal{O}(n^2m)$,与EK算法相同,但在稀疏图中远达不到这个复杂度。

优化——当前弧优化

如果一条边已经被增广过,那么它就没有再被增广第二次的可能性。因为只要在DFS中遍历到过这条边,那么经过这条边能引出的所有增广路都被增广过了,这条边不可能再被增广了。

这是一个很强的优化,能让Dinic算法跑的飞快。

实例

来自计蒜客Level 6课程。https://www.jisuanke.com/course/4728/287305

TODO.

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
    int v, c, fail;
} e[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int c) {
    e[eid].v = v;
    e[eid].fail = p[u];
    e[eid].c = c;
    p[u] = eid++;
}
void addedge(int u, int v, int c) {
    insert(u, v, c);
    insert(v, u, 0);
}
int S, T;
int d[MAX_N];
bool bfs() {
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(S);
    d[S] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = p[u]; i != -1; i = e[i].fail) {
            int v = e[i].v;
            if(e[i].c > 0 && d[v] == -1) {
                q.push(v);
                d[v] = d[u] + 1;
            }
        }
    }
    return (d[T] != -1);
}
int dfs(int u, int flow) {
    if(u == T) {
        return flow;
    }
    int res = 0;
    for(int i = p[u]; i != -1; i = e[i].fail) {
        int v = e[i].v;
        if(e[i].c > 0 && d[u] + 1 == d[v]) {
            int tmp = dfs(v, min(flow, e[i].c));
            flow -= tmp;
            e[i].c -= tmp;
            res += tmp;
            e[i ^ 1].c += tmp;
            if(flow == 0) {
                break;
            }
        }
    }
    if(res == 0) {
        d[u] = -1;
    }
    return res;
}
int Dinic() {
    int res = 0;
    while(bfs()) {
        res += dfs(S, INF);
    }
    return res;
}
int main() {
    int n, m;
    init();
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v, flow;
        cin >> u >> v >> flow;
        addedge(u, v, flow);
    }
    cin >> S >> T;
    cout << Dinic() << endl;
    return 0;
}

参考资料

网络流简介 – OI Wiki

网络流 – 计蒜客 Level 6 课程

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇