概念#

流网络$G=(V,E)$：一个有向图，有源点和汇点，每条边上的权值为流量，表示这条边每次能通过的最大流量。就好比有水从源点源源不断地流向汇点，在这个过程中，水会流向多个管道，但是每条管道都会有流量限制。不考虑反向边。如果有反向边，也可以通过加点的方式变成没有反向边。

可行流 $f$ ：满足 1. 容量限制 $0\le f(u,v) \le c(u,v)$，2. 流量守恒（除了源点和汇点之外，其余所有点都不存储流）$v,x \in \{V / \{s,t\} \} \ \ \sum_{(v,x)\in E} f(v,x) = \sum_{(x,v)\in E} f(x,v)$ 。这里不考虑反向边。$|f|$ 表示从源点到汇点的流量值是多少，或者说速率。$|f|=\sum_{(s,v)\in E}f(s,v) - \sum_{(v,s) \in E}f(v,s)$ ，简单地说就是源点往外流的流量减去往源点流的流量。

最大流 ：所有可行流中流量值最大的可行流，也就是最大可行流

残留网络$G_f$：残留网络是针对流网络的某一条可行流来说的，残留网络里面的点是原网络的点集，残留网络的边集是原来网络里面的边集和反向边集，权值的定义为：

残留网络可能也有可行流 $f^\prime$ ，原网络的可行流+残留网络的可行流也是原图的可行流，因此 $|f+f^\prime|=|f|+|f^\prime|$ 可行流相加等价于边相同方向则权值累加，边相反则原图边减去残留网络边的权值

$f+f^\prime$ 是否是原图可行流？判断是否满足容量限制和流量守恒即可

残留网络里面没有可行流，原网络可行流一定是最大流

增广路径： 在残留网络里面，沿着容量大于 $0$ 的边走，如果能走到终点，则这条路径被称为增广路径

割：将点集 $V$ 分成 $S$ 和 $T$ 两个子集，使得 $S\cup T = V$ 并且 $S \cap T = \emptyset$ ，$s \in S$，$t \in T$ 。换句话说，把点集分成不重的两个部分，源点在 $S$ 集中，汇点在 $T$ 集中，划分的这个结果称为图中的一个割。点集不一定连通。 任意图一共有 $2^{n-2}$ 个割

割的容量$c(S,T)$：指的是划分后的 $S$ 集中点到 $T$ 集中的边的权值之和

最小割：所有割中容量最小的割

割的流量$f(S,T)$：割的流量是对一个可行流来说的，就是 $S$ 到 $T$ 的边的所有可行流值减去 $T$ 到 $S$ 的边的所有可行流值

割的性质

1. 任意一个割$[S,T]$和任意一个流$f$，一定有 $f(S,T) \le c(S,T)$
2. 任意一个割$[S,T]$和任意一个流$f$，一定有 $f(S,T) = |f|$ 直观地思考一下，$s$ 流到 $t$ 的容量等价于 $S$ 流到 $T$ 的净流量

稍微证明：设 $f(X,Y) = \sum_{u\in X}\sum_{v \in Y} f(u,v) - \sum_{u\in X}\sum_{v \in Y} f(v,u)$ 那么，有$f(X,Y) = -f(Y,X)$，$f(X,X)=0$， 如果，$X\cap Y = \emptyset$，$f(Z,X\cup Y)=f(Z,X)+f(Z,Y)$，同样地 $f(X\cup Y,Z)=f(X,Z)+f(Y,Z)$ 因此，$f(S,V)=f(S,S)+f(S,T)$，也就是 $f(S,T)=f(S,V)$ 从而有

由于 $S - \{s\}$ 集合不包含源点 $s$ 和汇点 $t$，根据流量守恒，$f(S-\{s\},V)=0$ 因此 $f(S,T)=f(\{s\},V)=|f|$

推论3. 任意一个割$(S,T)$和任意一个流$f$，有 $|f| \le c(S,T)$

从而得知：最大流 $\le$ 最小割

最大流最小割定理： （1）可行流 $f$ 是最大流 （2）可行流 $f$ 的残留网络中不存在增广路 （3）存在某个割 $[S,T]$ ，$|f|=c(S,T)$ 三个条件两两等价

证明： （1）$\Longrightarrow$ （2）。可以用反证法证明，如果存在增广路，那么这个残留网络的可行流 $|f^\prime| \gt 0$ ，因此 $f+f^\prime$ 是一个更大的可行流，这与 $f$ 是最大流矛盾

（3）$\Longrightarrow$ （1）。根据上面的推论3，最大流 $\le c(S,T)$ ，而又因为有 $|f| = c(S,T)$ ，因此最大流 $\le |f|$ ，又根据定义 $|f| \le$ 最大流。从而，存在有某个割 $[S,T]$，$|f|=c(S,T)$ ，那么 $f$ 是最大流。从这里还能发现一个隐含的等于，由于最大流 $\le$ 最小割，又有 最小割 $\le c(S,T) = |f| \le$ 最大流。因此，最大流=最小割

（2）$\Longrightarrow$（3）。用构造来证明，就是在残留网络中不存在增广路能否构造出一个割，使得 $|f|=c(S,T)$。我们构造 $S$ 为在 $G_f$ 中沿着容量大于 0 的边所有能走到的点，$T = V - S$，这样子 $s\in S$，$t\in T$ 是一个合法的割。注意：割虽然是根据残留网络构造，但是划分里面的边还是原网络里面的边。

对于 $x \in S, y \in T$，如果 $(x,y) \in E$ ，那么 $f(x,y)=c(x,y)$，因为从构造角度来看，在残留网络中 $(x,y)$ 的权值为 $c(x,y)-f(x,y)$，如果这个值是大于0，则 $y \notin T$ ，这与划分矛盾。 同样地，对于 $a\in T, b \in S$，如果 $(a,b) \in E$，那么 $f(a,b)=0$，因为从构造的角度来看，在残留网络中，如果 $f(a,b) \gt 0$ ，那么其建立的反向边 $f(b,a)=f(a,b) > 0$ ，则 $a \notin T$ ，这与划分矛盾。

从而 $|f|=f(S,T)=\sum_{u\in S}\sum_{v \in T} f(u,v) - \sum_{u\in S}\sum_{v \in T} f(v,u) = \sum_{u\in S}\sum_{v \in T} f(u,v) = \sum_{u\in S}\sum_{v \in T} c(u,v)$

算法#

无论什么算法，都逃不过 FF 方法，也就是

1. 找增广路径
2. 更新残留网络 似乎有 ISAP 算法可替代，HLPP 算法优化很大，常用背 dinic 算法即可

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;
7

8
int n, m, S, T;
9
int h[N], e[M], ne[M], f[M], idx = 0;
10
bool st[N];
11
int d[N], q[N], pre[N];
12

13
void add(int a, int b, int c) {
14
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
15
}
16

17
int bfs() {
18
    memset(st, 0, sizeof st);
19
    int hh = 0, tt = 0;
20
    q[0] = S; st[S] = true; d[S] = INF;
21

22
    while (hh <= tt) {
23
        int u = q[hh ++ ];
24
        for (int i = h[u]; ~i; i = ne[i]) {
25
            int v = e[i];
26
            if (!st[v] && f[i]) {
27
                st[v] = true;
28
                d[v] = min(d[u], f[i]);
29
                pre[v] = i;
30
                if (v == T) return true;
31
                q[++ tt] = v;
32
            }
33
        }
34
    }
35
    return false;
36
}
37

38
int EK() {
39

40
    int ans = 0;
41
    while (bfs()) {
42
        ans += d[T];
43
        for (int i = T; i != S; i = e[pre[i] ^ 1])
44
            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
45
    }
46
    return ans;
47
}
48

49
int main() {
50

51
    memset(h, -1, sizeof h);
52

53
    cin >> n >> m >> S >> T;
54
    while (m -- ) {
55
        int a, b, c; cin >> a >> b >> c;
56
        add(a, b, c), add(b, a, 0);
57
    }
58

59
    cout << EK() << endl;
60
    return 0;
61
}

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 10010, M = 200010, INF = 0x3f3f3f3f;
7

8
int n, m, S, T;
9
int h[N], e[M], ne[M], f[M], idx = 0;
10
int q[N], d[N], cur[N];
11

12
void add(int a, int b, int c) {
13
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
14
}
15

16
bool bfs() {
17
    int hh = 0, tt = 0;
18
    memset(d, 0, sizeof d);
19
    d[S] = 1, q[0] = S, cur[S] = h[S];
20

21
    while (hh <= tt) {
22
        int u = q[hh ++ ];
23
        for (int i = h[u]; ~i; i = ne[i]) {
24
            int v = e[i];
25
            if (!d[v] && f[i]) {
26
                d[v] = d[u] + 1;
27
                cur[v] = h[v];
28
                if (v == T) return true;
29
                q[++ tt] = v;
30
            }
31
        }
32
    }
33
    return false;
34
}
35

36
int find(int u, int limit) {
37

38
    if (u == T) return limit;
39

40
    int flow = 0;
41
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
42
        cur[u] = i;
43
        int v = e[i];
44
        if (d[v] == d[u] + 1 && f[i]) {
45
            int t = find(v, min(f[i], limit - flow));
46
            if (!t) d[v] = 0;
47
            flow += t, f[i] -= t, f[i ^ 1] += t;
48
        }
49
    }
50
    return flow;
51
}
52

53
int dinic() {
54
    int r = 0, flow;
55
    while (bfs()) while (flow = find(S, INF)) r += flow;
56

57
    return r;
58
}
59

60
int main() {
61

62
    memset(h, -1, sizeof h);
63

64
    cin >> n >> m >> S >> T;
65

66
    while (m -- ) {
67
        int a, b, c; cin >> a >> b >> c;
68
        add(a, b, c); add(b, a, 0);
69
    }
70

71
    cout << dinic() << endl;
72
    return 0;
73
}

最大流模型#

最小割模型#

割：$[S,T]$ 割的流量 ：$f(S,T)$ 割的容量：$c(S,T)$

费用流模型#

费用流—所有最大可行流中费用最小/最大值：$\sum f(u,v)w(u,v)$

Q：图 $G$ 有最大流，是否一定有最小费用最大流？A：一定有

把 EK 算法中的 bfs 换成 spfa 即可求出费用流 一般情况下，要保证没有负权回路
假设正向边的费用是 $w(u,v)$，那么反向边的费用为 $-w(v,u)$ 只要原图没有负权回路，那么残留网络求最短路就没有负权回路

如果有负环回路，需要消圈法去解决