最大流要点
什么是最大流问题
总体是一张有向图，定一个源点，一个汇点。单位时间内源点能流出无限水，汇点能接受无限水。图中每条边相当于一个单位时间流量有限的管道。
最大流问题：单位时间内汇点最多能接收到多少水流？
解法
考虑贪心去做：反复 dfs 找到仍能流水的一条从源点到汇点的路径，路径中每个边的容量减去路径的最小容量（水管模型能流多少显然受最小容量限制吧...）。
但是好像不太对，有可能当前的一个流让它从另一个路径流出去更合适，借鉴反悔贪心的思想，我们可以给每条边加一条反向边。当一条边的容量被占据了 \(f\) 时，其容量减去 \(f\)，然后给它的反向边加上 \(f\)。
上面只是简单介绍了一下增广路的主要思想，下面是三种具体的求法。
OI 中网络流貌似不需要去管他的复杂度之类，尤其是最大流，卡 Dinic 的题可能只有 HLPP 模板题那一道。
主要是感性理解，重点都在建模。
EK
不会，上界 \(\operatorname{O}(nm^2)\)，懒得学了
Dinic
推荐结合这个博客看：https://www.cnblogs.com/SYCstudio/p/7260613.html
继续上面的贪心想法
每一次 dfs 可能得遍历整张图，只找到 1 条增广路，感觉不太值。
考虑多路增广。
dfs 每次传入两个参数：当前点编号和流过来了多少流量
原来的 dfs 过程：
- 判断当前是否到达汇点，如果到达汇点，返回当前流量。
- 否则枚举有流量的边，继续 dfs。
- dfs 如果返回正数，说明找到一条增广路，返回。
我们实际上可以在第 3 步找到增广路时不立即停止，而是将当前流量减去 dfs 返回的流量，表示有这么多的水已经流出去了。然后继续枚举边，枚举完毕/当前流量减到 0 则停止。
貌似会死循环，我们可以用 bfs 分层。每次 bfs 从源点开始，只走有流量的边，一个点的深度为到源点的最短距离。如果图不连通，说明找不到增广路了。
如果图连通，则反复 dfs。向下一个点搜索的前提是下一个点的深度 -1 等于当前点深度。
然后加一个当前弧优化：dfs 可能反复到达同一个点，而这个点的某些边可能已经被增广过了。因此在第一次到达该点的过程中，可以把链式前向星的 fir[nod] 修改为当前增广过但是还可能继续增广的边——之前的边增广过，流量没跑完，说明走那条边已经找不到增广路了。
每次分层情况都不一样，所以开一个 cur 数组当 fir 数组用，每次分层将 cur 数组的每个值都初始化成原 fir 数组的值。
示例代码：
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
| struct edge {
i64 u, v;
edge *nex, *opp;
i64 w;
} graph[M];
edge* tot = graph;
edge *fir[N], *cur[N];
i64 depth[N];
i64 n, m, s, t;
queue<i64> q;
void add(i64 a, i64 b, i64 c) {
++tot;
tot->u = a;
tot->v = b;
tot->w = c;
tot->opp = tot + 1;
tot->nex = fir[a];
fir[a] = tot;
++tot;
tot->u = b;
tot->v = a;
tot->w = 0;
tot->opp = tot - 1;
tot->nex = fir[b];
fir[b] = tot;
};
bool bfs() {
while (q.size())
q.pop();
cur[s] = fir[s];
for (int i = 1; i <= n; ++i)
depth[i] = 0;
depth[s] = 1;
q.push(s);
while (q.size()) {
i64 idx = q.front();
q.pop();
for (edge* e = fir[idx]; e; e = e->nex) {
if (e->w > 0 && !depth[e->v]) {
depth[e->v] = depth[idx] + 1;
q.push(e->v);
cur[e->v] = fir[e->v];
}
}
}
if (!depth[t]) return false;
return true;
}
i64 dfs(i64 nod, i64 val) {
if (nod == t) return val;
i64 res = 0;
for (edge* e = cur[nod]; e && val; e = e->nex) {
cur[nod] = e;
if (depth[nod] + 1 == depth[e->v] && e->w) {
i64 tmp = dfs(e->v, min(val, e->w));
if (tmp > 0) {
e->w -= tmp;
e->opp->w += tmp;
res += tmp;
val -= tmp;
} else if (!tmp)
depth[e->v] = -1;
}
}
return res;
}
i64 dinic() {
i64 res = 0;
i64 d = 0;
while () {
while (d = dfs(s, (i64)LLONG_MAX)) {
res += d;
}
}
return res;
}
|
ISAP
TODO
