网络流:最小割

网络流:最小割

将图 $G$ 分为 $A$ 和 $B$ 两个点集,$A$ 和 $B$ 之间的边的集合称为无向图的割集。带权图的割 (Cut) 就是割集中的边权之和。

S - T 最小割

特别地,对于一个网络,在满足 $源点 s \in 点集{S}, 汇点 t \in 点集{T}(S\cap T= \varnothing)$ 的情况下,从 S 到 T 的边的权值和被称为 S 到 T 的割

阅读更多
网络流:最大流

网络流:最大流

EK

增广路方法是很多网络流算法的基础。其思路是每次找出一条从源到汇的能够增加流的路径,调整流值和残留网络 ,直到没有增广路为止

EK 算法就是不断的找最短路,找的方法就是每次找一条边数最少的增广(即最短路径增广)。

最多要增广多少次?

可以证明,最多 O(VE)​ 次增广,可以达到最大流。

如何找到一条增广路?

先明确什么是增广路。增广路是一条从s到t的路径,路径上每条边残留容量都为正。把残留容量为正的边设为可行的边,那么我们就可以用简单的 BFS 得到边数最少的增广路。

阅读更多
网络流:模板

网络流:模板

P3376 网络最大流(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
67
68
69
70
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 11000, M = 110000;
const int INF = 0x7fffffff;
struct node {
int u, v, w, next;
} e[M << 1];
int cur[N], h[N], tot;
int dfn[N], ans, n, m, s, t;
void add(int u, int v, int w) {
e[tot] = node({u, v, w, h[u]});
cur[u] = h[u] = tot++;
}

bool bfs() {
memset(dfn, 0, sizeof dfn);
queue<int> q;
dfn[s] = 1;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = h[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(e[i].w and !dfn[v]) {
dfn[v] = dfn[u] + 1;
q.push(v);
if(v == t) return true;
}
}
}
return false;
}
int dfs(int u, int low) {
if(u == t) return low;
int w = low;
for(int i = cur[u]; i != -1; i = e[i].next) {
int v = e[i].v;
cur[u] = i;
if(e[i].w and dfn[v] == dfn[u] + 1) {
int f = dfs(v, min(w, e[i].w));
e[i].w -= f; e[i^1].w += f;
w -= f;
if(!w) break;
}
}
return low - w;
}
void dinic() {
while(bfs()) {
memcpy(cur, h, sizeof cur);
ans += dfs(s, INF);
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
memset(h, -1, sizeof h);
for(int i=1, u, v, w; i<=m; ++i) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, 0);
}
dinic();
printf("%d\n", ans);
return 0;
}

P3381 最小费用最大流(单路增广)

Dijkstra

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
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline

const int N = 5500, M = 55000, INF = 0x3f3f3f3f;

struct point {
int u, val;
point(int _u = 0, int _val = 0): u(_u), val(_val) {}
bool operator < (const point &o) const { return val > o.val; }
};

priority_queue <point> q;

struct node {
int u, v, w, f, next;
node() {}
} e[M << 1];
int head[N], tot = 0;

il void add(int u, int v, int w, int f) {
e[tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].f = f;
e[tot].next = head[u]; head[u] = tot++;
}

int h[N], dis[N], flow[N], pre[N];

int n, m, s, t;

int maxflow = 0, mincost = 0;
il bool dijkstra() {
memset(dis, 0x3f, sizeof dis);
memset(flow, 0x3f, sizeof flow);
memset(pre, -1, sizeof pre);

dis[s] = 0;
q.push(point(s, 0));
while (!q.empty()) {
int u = q.top().u, val = q.top().val;
q.pop();
if (val > dis[u]) continue;
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (e[i].w and dis[v] > dis[u] + e[i].f + h[u] - h[v]) {
pre[v] = i;
flow[v] = min(flow[u], e[i].w);
dis[v] = dis[u] + e[i].f + h[u] - h[v];
q.push(point(v, dis[v]));
}
}
}
return dis[t] != INF;
}

il void check() {

for (int p = pre[t]; p != -1; p = pre[e[p].u]) {
e[p].w -= flow[t];
e[p^1].w += flow[t];
}
maxflow += flow[t];
mincost += (dis[t] - h[s] + h[t]) * flow[t];

for(int i=1; i<=n; ++i) h[i] += dis[i];
}


int main() {

memset(head, -1, sizeof head);

scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i=1, u, v, w, f; i<=m; ++i) {
scanf("%d%d%d%d", &u, &v, &w, &f);
add(u, v, w, f);
add(v, u, 0, -f);
}

while (dijkstra()) check();
printf("%d %d\n", maxflow, mincost);

return 0;
}

SPFA

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 5500, M = 110000, INF = 0x3f3f3f3f;

struct node {
int u, v, w, f, next;
} e[M];
int h[N], tot = 0;

void add(int u, int v, int w, int f) {
e[tot] = {u, v, w, f, h[u]};
h[u] = tot++;
}

int pre[N], flow[N], dis[N];
bool vis[N];

int n, m, s, t, maxflow, mincost;

bool spfa() {

memset(pre, -1, sizeof pre);
memset(vis, false, sizeof vis);
memset(dis, 0x3f, sizeof dis);
memset(flow, 0x3f, sizeof flow);

queue<int> q;
q.push(s);
vis[s] = true;
dis[s] = 0;

while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int i = h[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(e[i].w and dis[v] > dis[u] + e[i].f) {
dis[v] = dis[u] + e[i].f;
pre[v] = i;
flow[v] = min(flow[u], e[i].w);
if(!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}

return dis[t] != INF;
}

void check() {
for(int p = pre[t]; p != -1; p = pre[e[p].u]) {
e[p].w -= flow[t];
e[p^1].w += flow[t];
}

mincost += dis[t] * flow[t];
maxflow += flow[t];
}
int main() {

scanf("%d%d%d%d", &n, &m, &s, &t);

memset(h, -1, sizeof h);
for(int i=1, u, v, w, f; i<=m; ++i) {
scanf("%d%d%d%d", &u, &v, &w, &f);
add(u, v, w, f);
add(v, u, 0, -f);
}

while(spfa()) check();

printf("%d %d\n", maxflow, mincost);

return 0;
}

LOJ115 无源汇有上下界可行流(超级源汇)

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
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline

const int N = 220, M = 11000, INF = 0x3f3f3f3f;

struct node {
int u, v, w, next;
} e[M * 6];

int head[N], cur[N], tot = 0;

il void add(int u, int v, int w) {
e[tot] = (node) {u, v, w, head[u]};
head[u] = tot++;
}

int h[N], n, m, ss, tt;
il bool bfs() { //分层

memset(h, 0, sizeof h);
memcpy(cur, head, sizeof cur);
queue<int> q;
q.push(ss);
h[ss] = 1;

while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(e[i].w and !h[v]) {
h[v] = h[u] + 1;
if(v == tt) return true;
q.push(v);
}
}
}
return false;
}

int dfs(int u, int low) {
if(u == tt) return low;
int w = low;
for(int i = cur[u]; i != -1; i = e[i].next, cur[u] = i) {
int v = e[i].v;
if(e[i].w and h[v] == h[u] + 1) {
int f = dfs(v, min(w, e[i].w));
e[i].w -= f;
e[i^1].w += f;
w -= f;
if(!w) break;
}
}
return low - w;
}

int tflow = 0, sflow = 0;
il void dinic() {

for(int i = head[ss]; i != -1; i = e[i].next)
sflow += e[i].w; //出流量

while(bfs()) dfs(ss, INF);

for(int i = head[tt]; i != -1; i = e[i].next)
tflow += e[i].w; //入流量

if(sflow == tflow) { //满流
printf("YES\n");
for(int i=0; i<tot; i+=6)
printf("%d\n", e[i+1].w + e[i+5].w); //反边流量和
} else printf("NO\n");

}
int main() {

freopen("loj115.in", "r", stdin);

scanf("%d%d", &n, &m);

memset(head, -1, sizeof head);
ss = 0, tt = n+1;
for(int i=1, u, v, l, h; i<=m; ++i) { //建图
scanf("%d%d%d%d", &u, &v, &l, &h);
add(u, tt, l);
add(tt, u, 0);
add(ss, v, l);
add(v, ss, 0);
add(u, v, h-l);
add(v, u, 0);
}

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 220, M = 22000, INF = 0x3f3f3f3f;

struct node {
int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
e[tot] = (node) {u, v, w, head[u]};
head[u] = tot++;
e[tot] = (node) {v, u, 0, head[v]};
head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {

memset(h, 0, sizeof h);
memcpy(cur, head, sizeof cur);

queue<int> q;
q.push(s);
h[s] = 1;

while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u], v; i != -1; i = e[i].next) {
v = e[i].v;
if(e[i].w and !h[v]) {
h[v] = h[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}

int dfs(int u, int low, int t) {
if(u == t) return low;

int w = low;
for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
v = e[i].v;
if(e[i].w and h[v] == h[u] + 1) {
int f = dfs(v, min(w, e[i].w), t);
e[i].w -= f;
e[i^1].w += f;
w -= f;
if(!w) break;
}
}
return low - w;
}

int main() {

//freopen("loj116.in", "r", stdin);

scanf("%d%d%d%d", &n, &m, &s, &t);

ss = 0, tt = n+1;
memset(head, -1, sizeof head);
for(int i=1, u, v, l, h; i<=m; ++i) {
scanf("%d%d%d%d", &u, &v, &l, &h);
in[u] -= l; in[v] += l;
add(u, v, h-l);
}

for(int i=1; i<=n; ++i) {
if(!in[i]);
else if(in[i] > 0) {
sflow += in[i];
add(ss, i, in[i]);
} else {
add(i, tt, -in[i]);
}
}

add(t, s, INF);

while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);

if(sflow != tflow) {
printf("please go home to sleep\n");
return 0;
}

for(int i = head[ss]; i != -1; i = e[i].next)
e[i].w = e[i^1].w = 0;

for(int i = head[tt]; i != -1; i = e[i].next)
e[i].w = e[i^1].w = 0;

int sum = e[--tot].w;
e[tot-1].w = e[tot].w = 0;

while(bfs(s, t)) sum += dfs(s, INF, t);

printf("%d\n", sum);

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 220, M = 22000, INF = 0x3f3f3f3f;

struct node {
int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
e[tot] = (node) {u, v, w, head[u]};
head[u] = tot++;
e[tot] = (node) {v, u, 0, head[v]};
head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {

memset(h, 0, sizeof h);
memcpy(cur, head, sizeof cur);

queue<int> q;
q.push(s);
h[s] = 1;

while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u], v; i != -1; i = e[i].next) {
v = e[i].v;
if(e[i].w and !h[v]) {
h[v] = h[u] + 1;
if(v == t) return true;
q.push(v);
}
}
}
return false;
}

int dfs(int u, int low, int t) {
if(u == t) return low;

int w = low;
for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
v = e[i].v;
if(e[i].w and h[v] == h[u] + 1) {
int f = dfs(v, min(w, e[i].w), t);
e[i].w -= f;
e[i^1].w += f;
w -= f;
if(!w) break;
}
}
return low - w;
}

int main() {

//freopen("loj116.in", "r", stdin);

scanf("%d%d%d%d", &n, &m, &s, &t);

ss = 0, tt = n+1;
memset(head, -1, sizeof head);
for(int i=1, u, v, l, h; i<=m; ++i) {
scanf("%d%d%d%d", &u, &v, &l, &h);
in[u] -= l; in[v] += l;
add(u, v, h-l);
}

for(int i=1; i<=n; ++i) {
if(!in[i]);
else if(in[i] > 0) {
sflow += in[i];
add(ss, i, in[i]);
} else {
add(i, tt, -in[i]);
}
}

add(t, s, INF);

while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);

if(sflow != tflow) {
printf("please go home to sleep\n");
return 0;
}

for(int i = head[ss]; i != -1; i = e[i].next)
e[i].w = e[i^1].w = 0;

for(int i = head[tt]; i != -1; i = e[i].next)
e[i].w = e[i^1].w = 0;

int sum = e[--tot].w;
e[tot-1].w = e[tot].w = 0;

while(bfs(s, t)) sum += dfs(s, INF, t);

printf("%d\n", sum);

return 0;
}
网络流:消圈算法

网络流:消圈算法

注:下文中的权均表示费用。

消圈定理

在某个流 $f$ 中,如果其残余网络中没有负圈(剩余流量为 $0$ 的边视为不存在),那它一定是当前流量下的最小费用,否则一定不是。

阅读更多
网络流:Dijkstra 求费用流

网络流:Dijkstra 求费用流

注:下文中的边权 $w$ 均表示费用 $f$。

Dijkstra 不能求有负权边的最短路,所以我们可以对网络 $G$ 中的每一个点设置一个势函数 $h(u)$,以满足在与原图等价的新图中的边权非负。

阅读更多