有上下界的网络流学习

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

无源汇有上下界可行流(也就是循环流)

模型

给定一个网络，求出一个流，是的每条边的流量满足[Li,Ri][L_i, R_i]，同时每个点的流入量==流出量

核心

将一个不满足流量守恒的初始流调整为满足流量守恒的流

思路

如果存在可行解，那么每条边的流量一定大于LiL_i，因此我们假设让每条边的初始流量为下限，得到一个初始流同时建立残余网络（每条边的流量为Ri−LiR_i-L_i）。但是初始流不一定满足流量守恒。

建立附加顶点SS,TTSS,TT后分以下三种情况

  • 流入量==流出量
  • 流入量≠\neq流出量
    • 流入量>>流出量，增加一条边到附加点TTTT
    • 流入量<<流出量，增加一条边从附加点到SSSS到当前点

其中SS、TTSS、TT的流量的绝对值一定相同

最后检查最大流是否为SSSS的所有流量即可

代码

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
134
135
136
137
138
139
140
141

//ZOJ2314   给定一个网络流模型，问否是每条边流量都能满足[L_i, R_i]  如果可以输出YES并且输出每条边的流量，否则输出NO
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
using ll = long long;
using db = double;

const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;

struct Dicnic {
    static const int M = 1e6 + 10;
    static const int N = 2e2 + 10;

    struct Edge {
        int to, nxt, flow;
    
        Edge() {}
    
        Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
    } edge[M << 1];
    
    int S, T;
    int head[N], dep[N], tot;
    
    void Init() {
        memset(head, -1, sizeof head);
        tot = 0;
    }
    
    void set(int _S, int _T) {
        S = _S, T = _T;
    }
    
    void addedge(int u, int v, int w, int rw = 0) {
        edge[tot] = Edge(v, head[u], w);
        head[u] = tot++;
        edge[tot] = Edge(u, head[v], rw);
        head[v] = tot++;
    }
    
    bool BFS() {
        memset(dep, -1, sizeof dep);
        queue<int> q;
        q.push(S);
        dep[S] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = edge[i].nxt) {
                if (edge[i].flow && dep[edge[i].to] == -1) {
                    dep[edge[i].to] = dep[u] + 1;
                    q.push(edge[i].to);
                }
            }
        }
        return dep[T] >= 0;
    }
    
    int DFS(int u, int f) {
        if (u == T || f == 0) return f;
        int w, used = 0;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
                w = DFS(edge[i].to, min(f - used, edge[i].flow));
                edge[i].flow -= w;
                edge[i ^ 1].flow += w;
                used += w;
                if (used == f) return f;
            }
        }
        if (!used) dep[u] = -1;
        return used;
    }
    
    int gao() {
        int res = 0;
        while (BFS()) {
            res += DFS(S, INF);
        }
        return res;
    }
} dicnic;

int n, m, low[N], totFlow[N];

void RUN() {
    memset(totFlow, 0, sizeof totFlow);
    scanf("%d %d", &n, &m);
    dicnic.Init();
    int S = 0, T = n + 1;
    dicnic.set(S, T);
    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d %d %d %d", &u, &v, low + i, &w);
        dicnic.addedge(u, v, w - low[i]);
        totFlow[u] -= low[i];
        totFlow[v] += low[i];
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (totFlow[i] >= 0) {
            sum += totFlow[i];
            dicnic.addedge(S, i, totFlow[i]);
        } else {
            dicnic.addedge(i, T, -totFlow[i]);
        }
    }
    int tmp = dicnic.gao();
    if (tmp == sum) {
        puts("YES");
        for (int i = 1; i <= m; ++i) {
            printf("%d\n", low[i] + dicnic.edge[2 * i - 1].flow);
        }
    } else {
        puts("NO");
    }
    puts("");
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        RUN();
    }

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

有源汇有上下界可行流

模型

现在的网络有一个源点SS和汇点TT,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制

核心

将有源汇右上下界可行流转换为无源汇上下界可行流

思路

由于存在S,TS, T两个点，他们的流入量≠\neq流出量，但是SS的流出量==TT的流出量，增加一条变T→ST\rightarrow S，流量为无限的边，就使得每个点的流入量等于流出量，在增加虚拟源汇点SS,TTSS,TT即可转换为无源汇右上下界可行流

有源汇有上下界最大流

模型

现在的网络有一个源点s和汇点t,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制.在这些前提下要求总流量最大

核心

先进行有源汇有上下界可行流判断，然后在残余网络上跑S−TS-T的最大流即可

思路

代码

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

// ZOJ 3229  一个人给m个女神拍照，总共拍摄n天，其中每天会给C个女神拍照，每天拍照限定数量为D，同时给每个女神拍照数量限制为[L_i, R_i], 对于每个女神拍照总数不能少于Gi，问总的拍照数量最大值
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
using ll = long long;
using db = double;

const int N = 1e3 + 10;
const int M = 2e3 + 10;
const int INF = 0x3f3f3f3f;

struct Dicnic {
    static const int M = 1e6 + 10;
    static const int N = 3e3 + 10;

    struct Edge {
        int to, nxt, flow;
    
        Edge() {}
    
        Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
    } edge[M << 1];
    
    int S, T;
    int head[N], dep[N], tot;
    
    void Init() {
        memset(head, -1, sizeof head);
        tot = 0;
    }
    
    void set(int _S, int _T) {
        S = _S, T = _T;
    }
    
    void addedge(int u, int v, int w, int rw = 0) {
        edge[tot] = Edge(v, head[u], w);
        head[u] = tot++;
        edge[tot] = Edge(u, head[v], rw);
        head[v] = tot++;
    }
    
    bool BFS() {
        memset(dep, -1, sizeof dep);
        queue<int> q;
        q.push(S);
        dep[S] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = edge[i].nxt) {
                if (edge[i].flow && dep[edge[i].to] == -1) {
                    dep[edge[i].to] = dep[u] + 1;
                    q.push(edge[i].to);
                }
            }
        }
        return dep[T] > 0;
    }
    
    int DFS(int u, int f) {
        if (u == T || f == 0) return f;
        int w, used = 0;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
                w = DFS(edge[i].to, min(f - used, edge[i].flow));
                edge[i].flow -= w;
                edge[i ^ 1].flow += w;
                used += w;
                if (used == f) return f;
            }
        }
        if (!used) dep[u] = -1;
        return used;
    }
    
    int gao() {
        int res = 0;
        while (BFS()) {
            res += DFS(S, INF);
        }
        return res;
    }
} dicnic;

int n, m, low[N][M], totFlow[N * M], pos[N][M];

void RUN() {
    memset(pos, -1, sizeof pos);
    memset(totFlow, 0, sizeof totFlow);
    int S = 0, T = n + m + 1;
    dicnic.Init();
    for (int i = 1, x; i <= m; ++i) {
        scanf("%d", &x);
        dicnic.addedge(i + n, T, INF - x);
        totFlow[i + n] -= x;
        totFlow[T] += x;
    }
    for (int i = 1, x, y; i <= n; ++i) {
        scanf("%d %d", &x, &y);
        dicnic.addedge(S, i, y);
        for (int j = 1, ith, up, down; j <= x; ++j) {
            scanf("%d %d %d", &ith, &down, &up);
            ++ith;
            pos[i][ith] = dicnic.tot;
            dicnic.addedge(i, n + ith, up - down);
            totFlow[i] -= down;
            totFlow[n + ith] += down;
            low[i][ith] = down;
        }
    }
    int sum = 0;
    dicnic.addedge(T, S, INF);
    int SS = n + m + 2, TT = n + m + 3;
    for (int i = S; i <= T; ++i) {
        if (totFlow[i] < 0) {
            dicnic.addedge(i, TT, -totFlow[i]);
        }
        if (totFlow[i] > 0) {
            sum += totFlow[i];
            dicnic.addedge(SS, i, totFlow[i]);
        }
    }
    dicnic.set(SS, TT);
    if (dicnic.gao() == sum) {
        dicnic.set(S, T);
        int res = dicnic.gao();
        printf("%d\n", res);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (pos[i][j] != -1) {
                    printf("%d\n", low[i][j] + dicnic.edge[pos[i][j] ^ 1].flow);
                }
            }
        }
    } else {
        puts("-1");
    }
    puts("");
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);

    while (scanf("%d %d", &n, &m) != EOF) {
        RUN();
    }

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

有源汇有上下界最小流

模型

现在的网络有一个源点s和汇点t,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制.在这些前提下要求总流量最小.

核心

跑完有源汇有上下界可行流后删除原图中的所有流量

思路

先跑出一个有源汇可行流，假如我们能在残量网络上找到一条S−TS-T的路径使得去掉这条路径上的流量之后仍然满足流量下限,我们就可以得到一个更小的流。

代码

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
134
135
136
137
138
139
140
141
142
143
144

//bzoj2502 给定一个DAG，每轮选择一个点开始清除一条路上的所有路径，问最小轮数
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
typedef long long ll;

const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;

struct Dicnic {
    static const int M = 1e6 + 10;
    static const int N = 3e3 + 10;

    struct Edge {
        int to, nxt, flow;
    
        Edge() {}
    
        Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
    } edge[M << 1];
    
    int S, T;
    int head[N], dep[N], tot;
    
    void Init() {
        memset(head, -1, sizeof head);
        tot = 0;
    }
    
    void set(int _S, int _T) {
        S = _S, T = _T;
    }
    
    void addedge(int u, int v, int w, int rw = 0) {
        edge[tot] = Edge(v, head[u], w);
        head[u] = tot++;
        edge[tot] = Edge(u, head[v], rw);
        head[v] = tot++;
    }
    
    bool BFS() {
        memset(dep, -1, sizeof dep);
        queue<int> q;
        q.push(S);
        dep[S] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = edge[i].nxt) {
                if (edge[i].flow && dep[edge[i].to] == -1) {
                    dep[edge[i].to] = dep[u] + 1;
                    q.push(edge[i].to);
                }
            }
        }
        return dep[T] > 0;
    }
    
    int DFS(int u, int f) {
        if (u == T || f == 0) return f;
        int w, used = 0;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
                w = DFS(edge[i].to, min(f - used, edge[i].flow));
                edge[i].flow -= w;
                edge[i ^ 1].flow += w;
                used += w;
                if (used == f) return f;
            }
        }
        if (!used) dep[u] = -1;
        return used;
    }
    
    int gao() {
        int res = 0;
        while (BFS()) {
            res += DFS(S, INF);
        }
        return res;
    }
    
    void Del(int u) {
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            edge[i].flow = edge[i ^ 1].flow = 0;
        }
    }
} dicnic;

int n, totFlow[N];

void RUN() {
    dicnic.Init();
    memset(totFlow, 0, sizeof totFlow);
    for (int i = 1, m; i <= n; ++i) {
        scanf("%d", &m);
        for (int j = 1, x; j <= m; ++j) {
            scanf("%d", &x);
            dicnic.addedge(i, x, INF);
            totFlow[i]--, totFlow[x]++;
        }
    }
    int S = 0, T = n + 1, SS = n + 2, TT = n + 3;
    for (int i = 1; i <= n; ++i) {
        dicnic.addedge(S, i, INF);
        dicnic.addedge(i, T, INF);
    }
    for (int i = 1; i <= n; ++i) {
        if (totFlow[i] < 0) {
            dicnic.addedge(i, TT, -totFlow[i]);
        } else {
            dicnic.addedge(SS, i, totFlow[i]);
        }
    }
    dicnic.addedge(T, S, INF);
    dicnic.set(SS, TT);
    dicnic.gao();
    int Max = dicnic.edge[dicnic.tot - 1].flow;
    dicnic.edge[dicnic.tot - 1].flow = dicnic.edge[dicnic.tot - 2].flow = 0;
    dicnic.Del(SS), dicnic.Del(TT);
    dicnic.set(T, S);
    printf("%d\n", Max - dicnic.gao());
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);
    while (scanf("%d", &n) != EOF) {
        RUN();
    }

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}