网络流学习笔记

网络流学习笔记

注：笔者比较菜，许多证明没有给出，一些地方可能有误。

一些定义

网络

对于一张有向图 $G \in (V, E)$，有一个源点 $S \in V$ 和一个汇点 $T \in V$，每一条边 $(u, v) \in E$ 有一个限流 $c(u, v)$。特别的，$\forall (u, v) \notin E \ , \ c(u, v) = 0$。

网络流

对于一个函数 $f(u, v)$，若满足如下性质：

  • $f(u, v) \le c(u, v)$，即流量小于限流；
  • $f(u, v) = -f(v, u)$，反边的流量等于这条边流量的相反数，为什么要有反边我们在下面解释；
  • $\forall x \in V - { S, \ T}, \ \sum {(u, x) \in E} f(u,x) = \sum{(x, u) \in E}f(x, u)$，从源点流出的流量等于流入汇点的流量；

则函数 $f(u, v)$ 被称为流函数。

最大流

求从源点出发，能够流到汇点的最大流量问题，称为最大流。

在了解求解算法之前，我们需要了解一些概念。

残量网络

$c(u, v)$ 在减去 $f(u, v)$ 后得到的剩余流量 $c’(u, v)$ 组成的网络被称为残量网络。这个网络可以比原图少一些边（$c(x, y) \neq 0, \ c’(x, y) = 0$），也可以有一些原图没有的边（反边）。

增广路

在残量网络的一条从 $S$ 到 $T$ 所有边剩余流量大于零的路径称为增广路。因为所有边剩余流量大于零，所以可以在增广路上在增加一些流量使得流更大，所以最大流的残量网络一定没有增广路。

EK (Edmonds-Karp) 算法

$\tt{EK}​$ 算法就是基于增广路的。算法的思想是每次 $\tt{bfs}​$ 找到一条增广路，并更新边权造出残量网络，更新答案，直到图中没有增广路。这里解释一下为什么要有反边，因为当前找到的增广路不一定是最优的，可能不包含在最大流的路径中，直接做就会出现错误。而反边给了我们反悔的机会，走反边就相当于减少了原来走这条边的流量，从而保证算法的正确性。

具体的，我们在残量网络上从源点 $S$ 开始 $\tt{bfs}$ ，每次走一直到汇点 $T$ 停止，记录路径上的的边的流量的最小值 $v$ 这样，就找到了一条增广路。接着重新走一遍增广路，每一条边的流量减去 $v$ ，反边流量加上 $v$ ，最后答案也加上 $v$，这样就找到了最大流。

TIP

如果你使用邻接表存图，那么有一个小技巧找到反边：我们都知道，$2$ 异或 $1$ 是 $3$，$3$ 异或 $1$ 是 $2$，因此可以用异或一的方法快速找到反边。

$\tt{EK}$ 的时间复杂度是 $O(nm^2)$，实际较快，能跑 $10^3$ ~ $10^4$ 的数据。

Dinic 算法

$\tt{EK}$ 一次只找到了一条增广路，存在较大的浪费，完全可以一次找到多条，就有了 $\tt{Dinic}$。

$\tt{Dinic}$ 的算法流程是这样的：

  • 通过 $\tt{bfs}$ 从源点 $S$ 对原图进行分层，构造分层图，直到汇点 $T$；
  • 从源点 $S$ 开始 $\tt{dfs}$，每次只走到层数比当前层数多一的点，找到当前分层图中的所有增广路并更新。

为什么要分层？通过分层可以找到最短路，最短路就可以避免一些问题，像这个图：

最短路就不会搞中间这条边了。以上纯属我口胡，我也不知道对不对。

实现中还有一些必要的优化，可以看下面的代码。经过优化的 $\tt{Dinic}$ 时间复杂度是 $\Theta(n^2m)$，实际跑时则更快，可以过 $10^4$ ~ $10^5$ 的数据。

CODE

$\tt{EK}$ 比较菜我就不放了 (〃´-ω･) 其实是懒得写，主要还是用 $\tt{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
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define N 210
#define M 5010
#define INF (1e9)
#define int long long
typedef int Array[N];

int n, m, S, T, Mx = 0, tot = 1;
Array hd, pre, flw, dep;

struct Edge {
	int y, v, to;
	Edge(int y = 0, int v = 0, int to = 0) :
		y(y), v(v), to(to) {}
}e[M * 2];

void addE(int x, int y, int v) {
	e[++ tot] = Edge(y, v, hd[x]), hd[x] = tot;
}

int bfs() { // bfs 求出分层
	queue<int> q;
	memset(dep, -1, sizeof dep);
	q.push(S),dep[S] = 0;
	while (q.size()) {
		int x = q.front(); q.pop();
		for (int i = hd[x]; i; i = e[i].to) {
			int y = e[i].y, v = e[i].v;
			if (v == 0 || dep[y] >= 0) continue;
			dep[y] = dep[x] + 1, q.push(y);
			if (y == T) return 1;
		}
	}
	return 0;
}

int dfs(int x, int in, int out = 0) {
	// in : 剩余流入的流量, out : 流出的流量
	if (x == T) return in; // 如果到达汇点直接返回
	for (int i = hd[x]; i; i = e[i].to){
		int y = e[i].y, v = e[i].v;
		if (dep[y] != dep[x] + 1 || v == 0) continue;
		// 如果 y 不是下一层或者无法流出就不用做了
		v = dfs(y, min(in, v));
		// 算出下面可以流到汇点的流量
		e[i].v -= v, e[i ^ 1].v += v;
		in -= v, out += v;
		if (!in) break; // 如果流量用完了就不用做了
	}
	if (!out) dep[x] = -1; // 流量用完了这个点就不用做了
	return out;
}

signed main() {
	n = read(), m = read(), S = read(), T = read();
	for (int i = 1; i <= m; i ++) {
		int x = read(), y = read(), v = read();
		addE(x, y, v), addE(y, x, 0);
	}

	while (bfs()) Mx+=dfs(S,1e9);

	printf("%lld\n", Mx);
	return 0;
}

这也是 模板题 AC 代码。

最大流求二分图最大匹配

源点 $S$ 连向左边的点，右边的点连向汇点 $T$，二分图无向边改为左边连向右边的边，所有边边权都为一，这样就把二分图最大匹配转换成了最大流。求方案可以遍历中间的边，若剩余流量为 $0$ 说明这条边被用了。

特别的，用 $\tt{Dinic}$ 求二分图最大匹配复杂度为 $\Theta(\sqrt nm)$ 。

CODE

给出建图部分以及求方案部分的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 建边
for (int i = 1; i <= m; i ++) {
	addE(S, i, 1);
}
for (int j = m + 1; j <= n; j ++) {
	addE(j, T, 1);
}
while (true) {
	int x = read(), y = read();
	if (x < 0 && y < 0) break;
	addE(x, y, 1);
}
// 求方案
for (int i = 2; i <= tot; i ++) {
	if (e[i].y == S || e[i ^ 1].y == S) continue;
	if (e[i].y == T || e[i ^ 1].y == T) continue;
	if (e[i].v == 0 && e[i].y > m) {
		printf("%d %d\n", e[i ^ 1].y, e[i].y);
	}
}

最小割

删去一些边，使得源点和汇点不连通，求删去的边流量之和最小的问题称为最小割。

结论：最小割 = 最大流，因此最小割代码和最大流一模一样。

参考：《算法竞赛进阶指南》，OI Wiki。