网络流初步

发表于 更新于 分类于

初学网络流，概念有点多
现在来梳理一下

yxc代码

源点，汇点

s表示源点，t表示汇点

流网络

  • 流网络是一张有向图，对于 ， 有属性
  • 容量类比于水管在单位时间内流过的最大水量

可行流

  • 容量限制：

  • 流量守恒：

  • 斜对称

注意：只有在残留网络中才有斜对称

  • 流函数

流出源点的水流流入源点的水流

  • 也是 的一个可行流，其中 表示在残留网络中的可行流

  • 若 即没有增广路时，则 为最大流

最大流

最大的可行流

残留网络

对原图 中的一个可行流而言，记为

其中

和中所有的反向边

残留网络的容量为

割

  • 将 不重不漏地分为两个子集 ，其中

  • 容量
    即从指向的边的容量和

  • 流量

  • 最小割
    容量最小的割

性质：

集合 , 的流量

即：

有性质：

  3. ，其中

最大流最小割定理

  1. 可行流 是最大流
  2. 中不存在增广路

以上命题等价

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
60
61
62
63
64
65
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000 + 10, M = 20000 + 10, INF = 1 << 29;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], idx;
int q[N], d[N], pre[N];
bool st[N];

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

bool bfs() {
    int hh = 0, tt = -1;
    memset(st, false, sizeof st);
    q[++ tt] = S;
    st[S] = true;
    d[S] = INF;
    
    while (hh <= tt) {
        int t = q[hh ++];
        // cout << t << endl;
        for (int i = h[t]; ~i; i = ne[i]) {
            // cout << "\t" + to_string(e[i]) << endl;
            int ver = e[i];
            if (!st[ver] && f[i]) {
                st[ver] = true;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                // printf("\t%d == %d is %s\n", ver, T,ver == t ? "Yes": "No");
                if (ver == T) return true;
                q[++ tt] = ver;
            }
        }
    }
    return false;
}

int ek() {
    int maxflow = 0;
    while (bfs()) {
        maxflow += d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) {
            f[pre[i]] -= d[T];
            f[pre[i] ^ 1] += d[T];
        }
    }
    return maxflow;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m --) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d\n", ek());
}

dinic 求最大流

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 = 1e5 + 10, M = N << 1, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], ne[M], f[M], idx;
int q[N], d[N], cur[N];

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

bool bfs() {
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh ++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int ver = e[i];
            if (d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[++ tt] = ver;
            }
        }
    }
    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 ver = e[i];
        if (d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[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() {
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m --) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d\n", dinic());
    return 0;
}

点分裂

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
#include <iostream>
#include <cstring>
#include <algorithm>

#define debug

using namespace std;

const int N = 55 << 1, M = (N * N) << 1, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], fs[M], idx;
bool g[N][N];
int q[N], cur[N], d[N];

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

bool bfs() {
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh ++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int ver = e[i];
            if (d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[++ tt] = ver;
            }
        }
    }
    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 ver = e[i];
        if (d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;    
        }
    }
    return flow;
}

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

void init() {
    memset(h, -1, sizeof h);
    memset(g, 0, sizeof g);
    memset(f, 0, sizeof f);
    idx = 0;
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();

        for (int i = 1; i <= m; ++ i) {
            int a, b;
            scanf(" (%d,%d)", &a, &b);
            a ++, b ++;
            add(a + n, b, INF);
            add(b + n, a, INF);
            g[a][b] = g[b][a] = true;
        }
        for (int i = 1; i <= n; ++ i) add(i, i + n, 1);
        memcpy(fs, f, sizeof f);

        int res = n;
        for (S = n + 1; S <= 2 * n; ++ S)
            for (T = S - n + 1; T <= n; ++ T)
                if (!g[S - n][T]) {
                    memcpy(f, fs, sizeof f);
                    res = min(res, dinic());
                }

        printf("%d\n", res);
    }
}