网络流
概念
网络流是一种抽象模型，它通常表示为一个有向图，其中节点代表各种资源的位置，边表示资源在节点之间的流动。每条边上都有一个容量，表示资源可以通过该边的最大数量。网络流问题的目标通常是找到从一个节点到另一个节点的流量分布，以最大化或最小化某种性能度量，例如最大流问题和最小割问题。
流（Flow）：表示资源在网络中的分配和传输。流量可以通过图中的边流动，但不能超过每条边的容量限制。容量（Capacity）：每条边上的容量表示该边允许的最大流量。流量不得超过容量。源点和汇点（Source and Sink）：源点是网络中资源的起始位置，汇点是资源的目标位置。网络流问题的目标通常是从源点到汇点传输最大量的资源。最大流问题（Maximum Flow Problem）：在给定网络中寻找从源点到汇点的最大流量，同时满足容量限制。最小割问题（Minimum Cut Problem）：在给定网络中找到一组边，通过删除这些边可以分离源点和汇点，同时最小化被切割的容量总和。
Ford-Fulkerson算法
Ford-Fulkerson算法是一种在网络流中寻找最大流的贪心算法。该算法通过不断寻找增广路径来增加流量，直到无法再找到增广路径为止。增广路径是一条从源点到汇点的路径，其中每条边都有剩余容量。剩余容量是指在当前流量下，边允许的额外流量。增广路径的流量是增广路径上剩余容量的最小值。
算法流程
-
初始化流量分布：开始时，将所有边的流量设为0。
-
寻找增广路径：在每一步中，算法尝试找到一条从源点到汇点的增广路径。增广路径是指一条路径，沿途的边都具有剩余容量（容量减去已经通过的流量），可以允许更多的流量通过。通常使用深度优先搜索（DFS）来查找增广路径。
-
更新流量：一旦找到增广路径，便可以算出路径可以通过的最大流量（即各边的最小值），算法将沿着这条路径减少剩余流量，同时增加反向边。
-
重复直到无法找到增广路径：算法重复执行步骤2和步骤3，直到不再存在增广路径为止。此时，流量分布将达到最大值。
-
计算最大流量：最后，计算从源点流出的总流量，即最大流量。
其实可以把反向边理解成一种撤销，走反向边就意味着撤回上次流经正向边的若干流量，这也合理解释了为什么扣除正向边容量时要给反向边加上相应的容量：反向边的容量意味着可以撤回的量。 加入了反向边这种反悔机制后，我们就可以保证，当找不到增广路的时候，流到汇点的流量就是最大流。
FF算法时间复杂度上界是O(e*f)，其中e为边数，f为最大流。最大流可能会很大，所以这个复杂度并不好。
Edmond-Karp算法
EK算法就是BFS实现的FF算法。
为什么在这里BFS通常比DFS的效果好？因为DFS很可能会“绕远路”，而BFS可以保证每次找到的都是最短的增广路。
它的复杂度上限是O(v*e^2)，其中v为点数，e是边数，这个算法至少与流的大小无关了。
EK算法可以通过洛谷P3376，而接下来的Dinic算法却有一个case无法通过
模板
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
| import java.util.*;
class EK {
private static final int INF = Integer.MAX_VALUE;
int last[], flow[];
int n, m, s, t, lv[], cur[], heads[], nexts[], tos[], weights[];
public EK(int n, int s, int t, int edges[][]) {
this.n = n; this.s = s; this.t = t;
m = edges.length;
int edgeNum = 1;
last = new int[n+1];
flow = new int[n+1];
lv = new int[n+1];
heads = new int[n+1];
cur = new int[n+1];
tos = new int[2*m + 2];
nexts = new int[2*m + 2];
weights = new int[2*m + 2];
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
++edgeNum;
nexts[edgeNum] = heads[u];
heads[u] = edgeNum;
tos[edgeNum] = v;
weights[edgeNum] = w;
++edgeNum;
nexts[edgeNum] = heads[v];
heads[v] = edgeNum;
tos[edgeNum] = u;
weights[edgeNum] = 0;
}
}
public boolean bfs() {
Arrays.fill(last, -1);
Deque<Integer> q = new LinkedList<>();
q.offer(s);
flow[s] = INF;
while (!q.isEmpty()) {
int p = q.poll();
if (p == t) {
break;
}
for (int eg = heads[p]; eg != 0; eg = nexts[eg]) {
int to = tos[eg], vol = weights[eg];
if (vol > 0 && last[to] == -1) {
last[to] = eg;
flow[to] = Math.min(flow[p], vol);
q.offer(to);
}
}
}
return last[t] != -1;
}
public long ek() {
long res = 0;
while (bfs()) {
res += flow[t];
for (int cur = t; cur != s; cur = tos[last[cur]^1]) {
weights[last[cur]] -= flow[t];
weights[last[cur]^1] += flow[t];
}
}
return res;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt(), m = sc.nextInt(), s = sc.nextInt(), t = sc.nextInt(), edges[][] = new int[m][3];
for (int i = 0; i < m; i++) {
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();
edges[i][2] = sc.nextInt();
}
EK d = new EK(n, s, t, edges);
System.out.println(d.ek());
}
}
}
|
Dinic算法
概念
Dinic算法使用层次图（Layered Graph）来改进最大流问题的求解。层次图是原网络图的一个子图，其中每个节点的高度（距离源点的最短路径长度）被计算出来。在层次图中，只有高度递增的边才能被增广，这有助于算法的快速收敛。
-
构建层次图：使用广度优先搜索（BFS）来构建层次图，计算每个节点的高度（层次）。只有在层次图中的边才能被增广。
-
寻找增广路径：在层次图上使用深度优先搜索（DFS）来查找从源点到汇点的增广路径。在DFS过程中，通过层次图中的边进行增广。
-
更新流量：一旦找到增广路径，便可以算出路径可以通过的最大流量（即各边的最小值），算法将沿着这条路径减少剩余流量，同时增加反向边。
-
重复步骤3和步骤4，直到无法找到从源点到汇点的增广路径为止。
-
计算最大流：计算从源点流出的总流量，即最大流。
模板
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
| public class Dinic {
int n, m, s, t, lv[], cur[], heads[], nexts[], tos[], weights[];
public Dinic(int n, int s, int t, int edges[][]) {
this.n = n; this.s = s; this.t = t;
m = edges.length;
int edgeNum = 1;
lv = new int[n+1];
heads = new int[n+1];
cur = new int[n+1];
tos = new int[2*m + 2];
nexts = new int[2*m + 2];
weights = new int[2*m + 2];
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
++edgeNum;
nexts[edgeNum] = heads[u];
heads[u] = edgeNum;
tos[edgeNum] = v;
weights[edgeNum] = w;
++edgeNum;
nexts[edgeNum] = heads[v];
heads[v] = edgeNum;
tos[edgeNum] = u;
weights[edgeNum] = 0;
}
}
public boolean bfs() {
Arrays.fill(lv, -1);
lv[s] = 0;
System.arraycopy(heads, 0, cur, 0, n);
Deque<Integer> q = new LinkedList<>();
q.offer(s);
while (!q.isEmpty()) {
int p = q.poll();
for (int eg = heads[p]; eg != 0; eg = nexts[eg]) {
int to = tos[eg], vol = weights[eg];
if (vol > 0 && lv[to] == -1) {
lv[to] = lv[p] + 1;
q.offer(to);
}
}
}
return lv[t] != -1;
}
public int dfs(int p, int flow) {
if (p == t) return flow;
int rmn = flow;
for (int eg = heads[p]; eg != 0 && rmn != 0; eg = nexts[eg]) {
int to = tos[eg], vol = weights[eg];
if (vol > 0 && lv[to] == lv[p] + 1) {
int c = dfs(to, Math.min(vol, rmn));
rmn -= c;
weights[eg] -= c;
weights[eg^1] += c;
}
}
return flow - rmn;
}
public long dinic() {
long res = 0;
while (bfs()) {
res += dfs(s, Integer.MAX_VALUE);
}
return res;
}
}
|
测试
洛谷P3376
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt(), m = sc.nextInt(), s = sc.nextInt(), t = sc.nextInt(), edges[][] = new int[m][3];
for (int i = 0; i < m; i++) {
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();
edges[i][2] = sc.nextInt();
}
Dinic d = new Dinic(n, s, t, edges);
System.out.println(d.dinic());
}
}
}
|
参考
