ISAP 和 Dinic 十分相似，应该比较好懂。

GAP 则是 ISAP 的优化。

简介

ISAP 算法，也是运用 BFS 分层 和 DFS 搜索。

与 Dinic 区别有两点：

  1. 只用了一次 BFS 分层，后续层数更新随着 DFS 一起
  2. 因为某些原因，DFS 需要反跑（汇点->源点）

过程

因为 ISAP 的 DFS 需要反跑，知道大家肯定打不习惯。

于是，我们可以反跑 BFS 分层，就可以正跑 DFS（反跑时汇点层数为 0）。

DFS 时，过程与 Dinic 基本相同，这里不详细展开。

更新层数

设 \(i\) 点的层数为 \(d_i\)。

当我们结束了一次 dfs（没有路可走），我们就要更新层数。

遍历 \(i\) 的所有连点，找到连点中最小的层数，记为 \(mind\)，则 \(d_i=mind+1\)。

若点 \(i\) 没有连点，则 \(d_i=n\)。

当 \(d_s\ge n\)，增广路已被搜完，结束循环。

优化

当前弧优化

详见 Dinic。

GAP

在 ISAP 算法的基础上，我们加一个数组 \(num\)，表示层数为 \(i\) 的点有多少个。

更新层数时同时也更新 \(num\)。

若一次更新后，\(num_i=0\)，说明图中出现断层，不需要再搜索，直接退出。

时间复杂度

时间复杂度：\(O(n^2m)\)。

虽然它与 Dinic 有着同样的理论复杂度，但实际上，GAP 在稠密图上更为优秀，Dinic 在稀疏图上更为优秀。

但是由于 Dinic 实在太好打了，而且网络流的题目一般 \(n\le 300\)，所以一般用 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
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
109
110
111
112
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int N = 1205, M = 120005;

constexpr ll LLINF = 1e18;

struct Graph {
    struct Edge {
        int v, nt;
        ll c;
    } e[M << 1];
    int hd[N], tot = 1;
    void add(int u, int v, ll c) { e[++tot] = {v, hd[u], c}, hd[u] = tot; }
    void uadd(int u, int v, ll c) { add(u, v, c), add(v, u, 0); }
} g;

int n, m;

namespace GAP {
int S, T;

bool vis[N];

int cur[N], dep[N], num[N];

int prep[N], pree[N];

void bfs() {
    queue<int> q;

    q.push(T);

    dep[T] = 0, vis[T] = 1, cur[T] = g.hd[T], num[0] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = g.hd[u]; i; i = g.e[i].nt) {
            int v = g.e[i].v;
            if (!vis[v] && g.e[i ^ 1].c) {
                cur[v] = g.hd[v];
                dep[v] = dep[u] + 1, vis[v] = 1, num[dep[v]]++;
                q.push(v);
            }
        }
    }
}

ll flow() {
    bfs();
    ll ans = 0, sum = LLINF;

    for (int i = 1; i <= n; i++) cur[i] = g.hd[i];

    int u = S;

    while (dep[S] < n) {
        if (u == T) {
            ans += sum;

            for (int x = T; x != S; x = prep[x]) {
                int i = pree[x];
                g.e[i].c -= sum, g.e[i ^ 1].c += sum;
            }

            u = S, sum = LLINF;
        }

        bool flag = 0;
        for (int i = cur[u]; i; i = g.e[i].nt) {
            int v = g.e[i].v;
            if (g.e[i].c && dep[u] == dep[v] + 1) {
                flag = 1;
                cur[u] = i;
                prep[v] = u, pree[v] = i;
                sum = min(sum, g.e[i].c);
                u = v;
                break;
            }
        }

        if (!flag) {
            int cnt = n - 1;
            for (int i = g.hd[u]; i; i = g.e[i].nt) {
                int v = g.e[i].v;
                if (g.e[i].c) cnt = min(cnt, dep[v]);
            }
            --num[dep[u]], dep[u] = cnt + 1, num[dep[u]]++;
            if (num[dep[u]] == 0) break;
            cur[u] = g.hd[u];
            if (u != S) u = prep[u];
        }
    }

    return ans;
}
} // namespace GAP

int main() {
    cin >> n >> m >> GAP::S >> GAP::T;

    for (int i = 1, u, v; i <= m; i++) {
        ll c;
        cin >> u >> v >> c, g.uadd(u, v, c);
    }

    cout << GAP::flow() << endl;

    return 0;
}

参考：oi-wiki