Sakana~
0%

【算法学习笔记】05 网络流

发表于 更新于 分类于

网络流笔记施工中…

目前进度：（1/1000）

（可能随时停止施工，因为太难了…

【算法学习笔记】05 网络流

入个大坑

1. 基本概念

1.1 流网络

1.2 可行流

流出 - 流入

1.2.3 最大流

最大可行流

1.3 残留网络

1.4 增广路径

残量网络中，沿着流量 >0 的边走可以走到终点的路径

1.5 割

1.6 算法

1.6.0 FF思想

维护残留网络
每次：找增广路 + 更新残留网络（正向 +k , 反向 -k）
存图：邻接表，正反向边成对存储

1.6.1 EK 算法

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
#include <bits/stdc++.h>

using namespace std;
const int N = 1005, M = 10005 * 2, inf = 1e9;
int n, m, S, T;
int h[N], e[M], ne[M], w[M], idx;
bool vis[N];
int d[N], pre[N];

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool bfs () {
    queue<int> q;
    memset (vis, false, sizeof vis);
    memset (d, 0, sizeof d);
    memset (pre, 0, sizeof pre);
    q.push (S), vis[S] = true, d[S] = inf;

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (vis[j] || w[i] == 0)    continue;
            pre[j] = i;
            vis[j] = true;
            d[j] = min (d[t], w[i]);

            if (j == T) return true;
            q.push (j);
        }
    }
    return false;
}

int EK () {
    int ans = 0;
    while (bfs ()) {
        ans += d[T];
        for (int i = T; i != S; i = e[pre[i]^1]) {
            w[pre[i]] -= d[T], w[pre[i]^1] += d[T];
        }
    }
    return ans;
}

int main () {
    memset (h, -1, sizeof h);
    cin >> n >> m >> S >> T;
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c), add (b, a, 0);
    }
    cout << EK() << endl;
}

1.6.2 Dinic 算法

不断找增广路。
优化之处在于，每次把可以增广的路全部增广一遍。
处理环：分层图

  1. bfs 建立分层图
  2. dfs 找出所有增广路径

当前弧优化：一条边增广一次后就不会再次增广了, 把h数组复制一份，不断更新增广的起点；
把已经流满的路径跳过：flow<limit；
无法达到汇点则退出

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
#include <bits/stdc++.h>

using namespace std;
const int N = 10005, M = 200005, inf = 1e9;
int n, m, S, T;
int h[N], e[M], ne[M], w[M], idx;
int d[N], cur[N];

void add (int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool bfs () {
    queue <int> q;
    memset (d, -1, sizeof d);
    q.push (S), d[S] = 0, cur[S] = h[S];
    while (!q.empty ()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] != -1 || w[i] == 0)    continue;
            d[j] = d[t] + 1;
            cur[j] = h[j];
            if (j == T) return true;
            q.push (j);
        }
    }
    return false;
}

int find (int u, int limit) {
    if (u == T)     return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i; //当前弧优化
        int j = e[i];
        if (d[j] != d[u] + 1 || w[i] == 0)  continue;
        int t = find (j, min (w[i], limit - flow));
        if (t == 0)     d[j] = -1;
        w[i] -= t, w[i^1] += t, flow += t;
    } 
    return flow;
}

int dinic () {
    int r = 0, flow;
    while (bfs ())  while (flow = find (S, inf))    r += flow;
    return r;
}

int main () {
    cin >> n >> m >> S >> T;
    memset (h, -1, sizeof h);
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c), add (b, a, 0);
    }
    cout << dinic () << endl;
}



//Dinic

1.7 应用

1.7.1 二分图

1. 二分图匹配
2. 二分图多重匹配

1.7.2 上下界网络流

1. 无源汇上下界可行流
2. 有源汇上下界最大流
3. 有源汇上下界最小流

1.7.3 多源汇最大流

题目

网络流24题

补充

EK求最大流
Pecco大大!
ctx大佬的板子