没进水的脑子


——博客——

网络流

  • ~9.13K 字
  1. 1. 对网络流的初步认识
    1. 1.1. 写在前面
  2. 2. 什么是网络流？
    1. 2.1. 引入
    2. 2.2. 定义
      1. 2.2.1. 流函数
    3. 2.3. 经典问题——网络最大流
      1. 2.3.1. Ford-Fulkerson方法
        1. 2.3.1.1. Edmonds-Karp算法
          1. 2.3.1.1.1. 复杂度分析：
        2. 2.3.1.2. Dinic算法
        3. 2.3.1.3. ISAP算法
    4. 2.4. 挖坑
  3. 3. 完结散花

对网络流的初步认识

写在前面

这是本蒟蒻写的第一篇博客，请各位巨佬多多包涵，欢迎指出文章的错误。

什么是网络流？

引入

在最短路算法的学习中，我们将多个地点之间的道路转化成有向图（或无向图）来处理各个地点的最短路问题。网络流问题也类似，我们可以将生活中比较常见的物料流动系统，比如管道网络、信息网络、电网、物流网络等视为网络流。从生活中的例子里我们发现，网络流问题就是一类处理物料从源点以稳定速率生成，并通过有容量上限的各个物流通道，最后流向汇点的问题。下面给出网络流的具体定义。

定义

网络流 G = ( V , E ) 是一个有向图，其中有N 个点、M 条边、源点S 、汇点T ，每条边 有一个非负的容量值 c ( u , v ) 0。

  • 举个栗子：
    示例来源于《算法导论》
    当然，除了表示容量值，我们还需要一个函数来定义当前流量，还有流之间的关系，接下来详细说一下流函数。

    流函数

    我们讲 定义为边的流量，并且满足一下性质：
  • 1.容量限制：
    对于所有结点 u , v V ,要求 。
  • 2.流量守恒：
    对于所有的节点 ，要求
    。
  • 3.斜对称：
    正向边的流量等于其对应反向边的流量

    经典问题——网络最大流

    既然已经明确了网络流的定义，那么不妨来看看这个最经典的网络流问题——网络最大流。通过上面的定义我们不难发现，在整个网络中存在多组流函数，其中使整个网络流量之和最大的流函数被称为最大流，此时的流量被称为最大流量。网络最大流问题既旨在寻找既定网络中的最大流量。


    为了处理最大流问题，我们伟大的先辈L.R.Ford和D.R.Fulkerson在1962年将原始-对偶算法应用于最大流问题，提出了Ford-Fulkerson方法（由于其方法有多种时间复杂度不同的算法实现，因此《算法导论》将其称为方法而不是算法，这里沿用此定义），下面引入相关概念。

Ford-Fulkerson方法

简单来说，Ford-Fulkerson方法就是不断搜索可行的路径，并更新残余网络。

  • 具体步骤：
    • 1.一开始所有边的容量都为0。
    • 2.根据网络流的三大性质，找到一条从s 到t的路径，并更新流量。
    • 3.重复（2）操作，直到无法找到满足三大性质的路径。

那么，根据这三个步骤，我们的程序是不是已经呼之欲出了呢？ 诶，如果你只按这三个步骤搜索的话，或许已经发现这个程序会有一些错误，举个例子。
如果搜索到的第一条路径为 $ S -> a -> b -> T$
更新后得到此图
很明显，我们已经没有办法找到其他符合要求的路径了，该网络流的最大流为1，但是我们得到的最大流并不是真正的答案，如果先走再走的话，该网络的最大流为2。究其原因，在的路径中边占据了之后的流量，我们可以认为这是一次 “错误” 的搜索，为了防止这种 “错误” 对以后产生影响，我们引入残留网络的概念。

  • 残留网络：
    在每次搜索后，在经过的路径上反补一条与该路径方向相反的路径，形成的新图就叫残留网络。

这个过程可以理解为在每次搜索后建立一条用来 “反悔” 的路径，以保证之后的搜索不受 “错误” 查找的影响。Ford-Fulkerson方法就是基于残留网络和反补路径实现的。后文将详细讲述几个基于Ford-Fulkerson方法的算法

Edmonds-Karp算法

EK算法是最典型的实现方式，按照Ford-Fulkerson的思路实现即可。为了防止在搜索时出现不断搜索一条路径的情况，我们用BFS实现。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f;
const int M = 11000;
const int N = 300;
int cnt = 1;
struct edge
{
    int u, v, c, nxt;
    edge(int u = 0, int v = 0, int c = 0, int nxt = 0) : u(u), v(v), c(c), nxt(nxt) {}
} e[M];
int head[N];
void add_edge(int u, int v, int c)
{
    cnt++;
    e[cnt] = edge(u, v, c, head[u]);
    head[u] = cnt;
}
int pre[N];
int re[N];
int flow[N];
int bfs(int s, int t)
{
    memset(pre, -1, sizeof pre);
    flow[s] = INF;
    pre[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if (u == t)
            break;
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (v == s || e[i].c == 0 || pre[v] != -1)
                continue;
            pre[v] = u;
            re[v] = i;
            q.push(v);
            flow[v] = min(flow[u], e[i].c);
        }
    }
    if (pre[t] == -1)
        return -1;
    return flow[t];
}
int maxflow(int s, int t)
{
    int mx = 0;
    while (1)
    {
        int f = bfs(s, t);
        if (f == -1)
            break;
        int cur = t;
        while (cur != s)
        {
            e[re[cur]].c -= f;
            e[re[cur] ^ 1].c += f; // 存边小技巧
            cur = pre[cur];
        }
        mx += f;
    }
    return mx;
}
int n, m;
signed main()
{
    int s = 0, t = 0;
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        add_edge(u, v, c);
        add_edge(v, u, 0);
    }
    cout << maxflow(s, t);
}

复杂度分析：

EK查找增广路的总时间为 ,一次BFS时间为 ,所以总时间为 ,

Dinic算法

在EK中，每次搜索都要重新找到一条由S到T的增广路，这样的复杂的显然是不可以接受的。在Dinic算法中，实现了一次对多条增广路的搜索。

  • Dinic思想：
    • 1.BFS分层，记录每个节点最早被搜索到的深度。
    • 2.DFS在分层图上搜索，每次只能搜索到下一个深度的邻居结点，找到一条从当前结点v到汇点T的路径，并在回溯时更新流量。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, s, t;
const int INF = 0x3f3f3f3f;
const int M = 11000;
const int N = 220;
int cnt = 1;
int head[N];
struct Edge
{
    int u, v, c, nxt;
    Edge(int u = 0, int v = 0, int c = 0, int nxt = 0) : u(u), v(v), c(c), nxt(nxt) {}
} e[M];
void add_edge(int u, int v, int c)
{
    cnt++;
    e[cnt] = Edge(u, v, c, head[u]);
    head[u] = cnt;
}
int now[N]; // 用于存副本
int dep[N]; // 记录高度
bool bfs(int s, int t)
{
    for (int i = 1; i <= n; i++)
        dep[i] = INF;
    dep[s] = 0;
    now[s] = head[s]; // 弧优化，感兴趣可以自行搜索
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int c = e[i].c;
            int v = e[i].v;
            if (!c || dep[v] != INF)
                continue;
            q.push(v);
            now[v] = head[v];
            dep[v] = dep[u] + 1; // 更新结点深度
            if (v == t)
                return 1; // 找到汇点
        }
    }
    return 0; // 若未找到汇点，则说明无法找到新的合法路径，退出搜索。
}
int dfs(int u, int sum)
{
    if (u == t)
        return sum;
    int nowflow = 0;
    for (int i = now[u]; i; i = e[i].nxt)
    {
        now[u] = i;
        int v = e[i].v;
        int c = e[i].c;
        if (!c || (dep[v] != dep[u] + 1))
            continue;
        int k = dfs(v, min(c, sum));
        if (k == 0)
            dep[v] = INF; // 小剪枝，将已经不能增广的点去掉
        e[i].c -= k;
        e[i ^ 1].c += k; // 更新残留网络
        nowflow += k;    // 表示经过该点的流量
        sum -= k;        // 表示剩余流量
    }
    return nowflow;
}
int maxflow(int s, int t)
{
    int mx = 0;
    while (bfs(s, t))
        mx += dfs(s, INF);
    return mx;
}
signed main()
{
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        add_edge(u, v, c);
        add_edge(v, u, 0);
    }
    cout << maxflow(s, t);
    return 0;
}
趣味小知识

算法来源于苏联学者Yefim Dinitz1970年发表的论文，但是这篇文章由于收到刊物篇幅限制写的过于简短，晦涩难懂，后来被两位美国学者解释、实现并大力推荐，但是误把Dinitz拼成Dinic。Dinitz在2006年写了一篇文章来解释这个算法的来龙去脉。虽然Dinic算法看起来像是对EK算法的改进，但其实EK算法的出现要比Dinic算法晚两年（1972）。

ISAP算法

ISAP算法是对Dinic算法的进一步改进，在Dinic中，我们进行了多次BFS分层，而ISAP只需要一次BFS分层，然后再分层图上多次寻找增广路，为了更新残留网络，ISAP直接在原分层图上修改，而不是像Dinic一样进行多次BFS，因此有更优秀的复杂度。

  • ISAP思想：
    • 1.从汇点T开始BFS，记录每个节点到T的距离，可以理解为高度。
    • 2.从源点S开始DFS，在寻找路径时，按从高到低的顺序递减搜索，在s的邻居节点中，从高度比s小的节点开始搜索，每次搜索高度减1，到达汇点T后回溯，更新残留网络。
    • 3.回到s,若无法找到高度低于s的节点，则将s的高度提升到最低的邻居节点的高度加1的高度，若某一高度出现断层（即该高度没有节点），则说明没有新的增广路，退出搜索。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, s, t;
const int M = 11000;
const int N = 220;
int cnt = 1;
int head[N], now[N];
int dep[N]; // 用于存高度
int pre[N];
int gap[M]; // 存该高度上的节点数量
struct Edge
{
    int u, v, c, nxt;
    Edge(int u = 0, int v = 0, int c = 0, int nxt = 0) : u(u), v(v), c(c), nxt(nxt) {}
} e[M];
void add_edge(int u, int v, int c)
{
    cnt++;
    e[cnt] = Edge(u, v, c, head[u]);
    head[u] = cnt;
}
void bfs(int s, int t)
{
    memset(gap, 0, sizeof gap);
    memset(dep, 0, sizeof dep);
    dep[t] = 1; // 为了以后判断方便，这里将T点的高度设置为1
    queue<int> q;
    q.push(t);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        gap[dep[u]]++;
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            int c = e[i].c;
            if (dep[v] || c)
                continue; // 因为是从下往上BFS，所以只处理反边
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
}
int Augment() // 更新残留网络
{
    int v = t, flow = INF;
    while (v != s)
    {
        int i = pre[v];
        flow = min(flow, e[i].c);
        v = e[i].u;
    }
    v = t;
    while (v != s)
    {
        int i = pre[v];
        e[i].c -= flow;
        e[i ^ 1].c += flow;
        v = e[i].u;
    }
    return flow;
}
int maxflow(int s, int t) // 这里用非递归实现ISAP
{
    int mx = 0;
    bfs(s, t);
    int u = s;
    memcpy(now, head, sizeof head); // 存副本，还是当前弧优化
    while (dep[s] <= n)
    {
        if (u == t)
        {
            mx += Augment();
            u = s;
        }
        bool can = 0;
        for (int i = now[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            int c = e[i].c;
            if (!c || dep[v] + 1 != dep[u])
                continue;
            can = 1;
            pre[v] = i;
            now[u] = i;
            u = v;
            break;
        }
        if (!can)
        {
            if (!--gap[dep[u]])
                break; // 该深度没有节点，退出搜索
            int mi = n + 1;
            for (int i = head[u]; i; i = e[i].nxt)
            {
                int v = e[i].v;
                if (!e[i].c)
                    continue;
                mi = min(mi, dep[v]);
            }
            dep[u] = mi + 1;
            gap[dep[u]]++;
            now[u] = head[u]; // 记录当前弧
            if (u != s)
                u = e[pre[u]].u; // 类似于DFS的回溯
        }
    }
    return mx;
}
using namespace std;
signed main()
{
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        add_edge(u, v, c);
        add_edge(v, u, 0);
    }
    cout << maxflow(s, t);
    return 0;
}

挖坑

  • [x] 预留推进
  • [x] 费用流
  • [ ] 二分图匹配，最小割

完结散花

由于本人是第一次写博客，如果有任何问题（排版，思路，代码等），欢迎留言。

  • 作者邮箱：2759094765@qq.com