Skip to content

上下界网络流学习笔记

笔记约 2.1 千字
# 图论 # 网络流 # 上下界网络流 # 最大流 # 可行流
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#前置知识

#无源汇上下界可行流

给定无源汇流量网络 GG。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时每一个点流量平衡。

#实现

先强制初始流存在，这样有的点的入流不等于出流，这样对应的和 S,TS, T 连边（边权为出入流量差），原图的边容量为剩余流量。

具体来说，设 Δi\Delta_i 为第 ii 个点的入流与出流之差。若 Δi>0\Delta_i > 0，连 SS 到 ii；否则连 ii 到 TT。权值均为 ∣Δi∣|\Delta_i|。当存在最大流使得 SS 的所有出边都满流，则有解。

对于有源汇上下界可行流，只需要连一条 T→ST \to S、容量无穷大的边就可以将其转化为无源汇上下界可行流。

#代码

C++
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
#include <iostream>
#include <cstring>
#include <limits>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 205,
          M = 10205;

int n, m, s, t;
int idx, head[N], ver[M << 2], next[M << 2];
std::pair<int, int> edge[M << 2];
int f[N], d[N], cur[N];

void add(int u, int v, int a, int b) {
    ver[idx] = v;
    edge[idx] = std::make_pair(a, b);
    next[idx] = head[u];
    head[u] = idx++;
}

bool bfs() {
    memset(d, 0x00, sizeof(d));

    std::queue<int> q;
    q.push(s);
    d[s] = 1;
    cur[s] = head[s];

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

        for (int i = head[u]; ~i; i = next[i]) {
            int v = ver[i];

            if (!d[v] && edge[i].first) {
                d[v] = d[u] + 1;
                cur[v] = head[v];
                if (v == t) return true;
                q.push(v);
            }
        }
    }

    return false;
}

int dinic(int u, int limit) {
    if (u == t) return limit;

    int flow = 0;
    for (int &i = cur[u]; ~i && flow < limit; i = next[i]) {
        int v = ver[i];

        if (d[v] == d[u] + 1 && edge[i].first) {
            int k = dinic(v, std::min(edge[i].first, limit - flow));
            if (!k) d[v] = 0;
            edge[i].first -= k;
            edge[i ^ 1].first += k;
            flow += k;
        }
    }

    return flow;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(head, 0xff, sizeof(head));

    cin >> n >> m;

    for (int i = 1, u, v, a, b; i <= m; i++) {
        cin >> u >> v >> a >> b;

        add(u, v, b - a, a);
        add(v, u, 0, 0);

        f[u] -= a, f[v] += a;
    }

    int sum = 0;
    s = 0, t = n + 1;

    for (int i = 1; i <= n; i++) {
        if (f[i] > 0) {
            add(s, i, f[i], 0);
            add(i, s, 0, 0);
            sum += f[i];
        } else if (f[i] < 0) {
            add(i, t, -f[i], 0);
            add(t, i, 0, 0);
        }
    }

    int res = 0, flow;
    while (bfs()) {
        while (flow = dinic(s, std::numeric_limits<int>::max())) res += flow;
    }

    if (res == sum) {
        cout << "YES" << endl;

        for (int i = 0; i < m << 1; i += 2) {
            cout << edge[i ^ 1].first + edge[i].second << endl;
        }
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

#有源汇上下界最大流

给定有源汇流量网络 GG。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。如果存在，询问满足标定的最大流量。

#实现

先找到网络上的任意一个可行流，如果无解可以直接结束。

如果可行流有解，那么先删去求可行流时添加的超级源汇点、T→ST \to S 的辅助边，再在残量网络上跑一遍 S→TS \to T 的最大流，最后将可行流流量与最大流流量相加即可。

#代码

C++
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
127
128
#include <iostream>
#include <cstring>
#include <limits>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 205,
          M = 10205;

int n, m, s, t, ss, tt;
int idx, head[N], ver[M << 2], edge[M << 2], next[M << 2];
int f[N], d[N], cur[N];

void add(int u, int v, int w) {
    ver[idx] = v;
    edge[idx] = w;
    next[idx] = head[u];
    head[u] = idx++;
}

bool bfs() {
    memset(d, 0x00, sizeof(d));

    std::queue<int> q;
    q.push(s);
    d[s] = 1;
    cur[s] = head[s];

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

        for (int i = head[u]; ~i; i = next[i]) {
            int v = ver[i],
                w = edge[i];

            if (!d[v] && w) {
                d[v] = d[u] + 1;
                cur[v] = head[v];
                if (v == t) return true;
                q.push(v);
            }
        }
    }

    return false;
}

int dinic(int u, int limit) {
    if (u == t) return limit;

    int flow = 0;
    for (int &i = cur[u]; ~i && flow < limit; i = next[i]) {
        int v = ver[i],
            w = edge[i];

        if (d[v] == d[u] + 1 && w) {
            int k = dinic(v, std::min(w, limit - flow));
            if (!k) d[v] = 0;
            edge[i] -= k;
            edge[i ^ 1] += k;
            flow += k;
        }
    }

    return flow;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(head, 0xff, sizeof(head));

    cin >> n >> m >> ss >> tt;

    for (int i = 1, u, v, a, b; i <= m; i++) {
        cin >> u >> v >> a >> b;

        add(u, v, b - a);
        add(v, u, 0);

        f[u] -= a, f[v] += a;
    }

    int sum = 0;
    s = 0, t = n + 1;

    for (int i = 1; i <= n; i++) {
        if (f[i] > 0) {
            add(s, i, f[i]);
            add(i, s, 0);
            sum += f[i];
        } else if (f[i] < 0) {
            add(i, t, -f[i]);
            add(t, i, 0);
        }
    }

    add(tt, ss, std::numeric_limits<int>::max());
    add(ss, tt, 0);

    int res = 0, flow;
    while (bfs()) {
        while (flow = dinic(s, std::numeric_limits<int>::max())) res += flow;
    }

    if (res == sum) {
        int x = edge[idx - 1];
        edge[idx - 1] = edge[idx - 2] = 0;

        s = ss, t = tt;

        int res = 0, flow;
        while (bfs()) {
            while (flow = dinic(s, std::numeric_limits<int>::max())) res += flow;
        }

        cout << x + res << endl;
    } else {
        cout << "please go home to sleep" << endl;
    }

    return 0;
}

#有源汇上下界最小流

给定有源汇流量网络 GG。询问是否存在一种标定每条边流量的方式，使得每条边流量满足上下界同时除了源点和汇点每一个点流量平衡。如果存在，询问满足标定的最小流量。

#实现

与有源汇上下界最大流类似。

先找到网络上的任意一个可行流，如果无解可以直接结束。

如果可行流有解，那么先删去求可行流时添加的超级源汇点、T→ST \to S 的辅助边，再在残量网络上跑一遍 T→ST \to S 的最大流，最后用可行流流量减去最大流流量即为最小流。

#代码

C++
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
127
128
129
130
131
132
133
#include <iostream>
#include <cstring>
#include <fstream>
#include <limits>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e4 + 5,
          M = 125003 + 5;

int n, m, s, t, ss, tt;
int idx, head[N], ver[M << 2], edge[M << 2], next[M << 2];
int f[N], cur[N], dist[N];

void add(int u, int v, int w) {
    ver[idx] = v;
    edge[idx] = w;
    next[idx] = head[u];
    head[u] = idx++;
}

bool bfs() {
    memset(dist, 0x00, sizeof(dist));

    std::queue<int> q;

    q.push(s);
    dist[s] = 1;
    cur[s] = head[s];

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

        for (int i = head[u]; ~i; i = next[i]) {
            int v = ver[i],
                w = edge[i];

            if (!dist[v] && w) {
                dist[v] = dist[u] + 1;
                cur[v] = head[v];
                if (v == t) return true;
                q.push(v);
            }
        }
    }

    return false;
}

int dinic(int u, int limit) {
    if (u == t) return limit;

    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = next[i]) {
        cur[u] = i;

        int v = ver[i],
            w = edge[i];

        if (dist[v] == dist[u] + 1 && w) {
            int k = dinic(v, std::min(w, limit - flow));

            if (!k) dist[v] = 0;
            edge[i] -= k;
            edge[i ^ 1] += k;
            flow += k;
        }
    }

    return flow;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(head, 0xff, sizeof(head));

    cin >> n >> m >> ss >> tt;

    for (int i = 1, u, v, a, b; i <= m; i++) {
        cin >> u >> v >> a >> b;

        add(u, v, b - a);
        add(v, u, 0);

        f[u] -= a, f[v] += a;
    }

    int sum = 0;
    s = 0, t = n + 1;

    for (int i = 1; i <= n; i++) {
        if (f[i] > 0) {
            add(s, i, f[i]);
            add(i, s, 0);
            sum += f[i];
        } else if (f[i] < 0) {
            add(i, t, -f[i]);
            add(t, i, 0);
        }
    }

    add(tt, ss, std::numeric_limits<int>::max());
    add(ss, tt, 0);

    int res = 0, flow;
    while (bfs()) {
        while (flow = dinic(s, std::numeric_limits<int>::max())) res += flow;
    }

    if (res == sum) {
        int x = edge[idx - 1];
        edge[idx - 1] = edge[idx - 2] = 0;

        s = tt, t = ss;

        int res = 0, flow;
        while (bfs()) {
            while (flow = dinic(s, std::numeric_limits<int>::max())) res += flow;
        }

        cout << x - res << endl;
    } else {
        cout << "please go home to sleep" << endl;
    }

    return 0;
}

#参考资料

  1. 最大流之上下界可行流，AcWing 算法进阶课，闫学灿，2020 年 7 月 31 日。
  2. 上下界网络流，OI Wiki，2021 年 2 月 8 日。