网络流与二分图匹配：从CSP-S到IOI#

网络流是图论中最重要的算法之一，广泛应用于资源分配、任务调度、匹配问题等场景。本文将系统介绍从入门到进阶的网络流算法体系。

一、网络流基本概念#

1.1 流网络定义#

流网络是一个有向图 $G=(V,E)$ ，其中：

每条边 $(u,v) \in E$ 有一个非负容量 $c(u,v) \geq 0$
存在源点 $s$ 和汇点 $t$ ，其中 $s$ 没有入边， $t$ 没有出边
对于不存在的边 $(u,v) \notin E$ ，规定 $c(u,v) = 0$

1.2 流的性质#

流 $f$ 是定义在边集上的函数，满足：

容量限制： $\forall (u,v) \in E, 0 \leq f(u,v) \leq c(u,v)$

流量守恒： $\forall u \in V - \{s,t\}, \sum_{v \in V} f(v,u) = \sum_{v \in V} f(u,v)$

流的值定义为： $|f| = \sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s)$

1.3 残量网络与增广路#

残量网络 $G_f$ 中，每条边的残量容量为： $c_f(u,v) = c(u,v) - f(u,v)$

增广路是残量网络中从 $s$ 到 $t$ 的一条路径，沿途所有边的残量容量都大于0。

增广路定理：流 $f$ 是最大流当且仅当残量网络 $G_f$ 中不存在增广路。

二、最大流算法#

2.1 Ford-Fulkerson 方法#

Ford-Fulkerson 是一种框架性方法，核心思想是不断寻找增广路并增广。

算法流程：

初始化流 $f$ 为 0
当存在增广路 $p$ $p$ 时：
- 计算 $p$ 的残量容量 $c_f(p) = \min\{c_f(u,v) : (u,v) \in p\}$
- 沿 $p$ 增广流量 $c_f(p)$
返回流 $f$

时间复杂度： $O(E \cdot |f^*|)$ ，其中 $|f^*|$ 是最大流的值。

2.2 Edmonds-Karp 算法#

使用BFS寻找最短增广路的Ford-Fulkerson实现。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int MAXN = 1005;
5
const int INF = 1e9;
6

7
struct Edge {
8
    int to, cap, rev;
9
};
10

11
vector<Edge> graph[MAXN];
12
int level[MAXN], iter[MAXN];
13
int n, m, s, t;
14

15
void add_edge(int from, int to, int cap) {
16
    graph[from].push_back({to, cap, (int)graph[to].size()});
17
    graph[to].push_back({from, 0, (int)graph[from].size() - 1});
18
}
19

20
bool bfs() {
21
    memset(level, -1, sizeof(level));
22
    queue<int> q;
23
    q.push(s);
24
    level[s] = 0;
25

26
    while (!q.empty()) {
27
        int u = q.front();
28
        q.pop();
29

30
        for (auto& e : graph[u]) {
31
            if (e.cap > 0 && level[e.to] < 0) {
32
                level[e.to] = level[u] + 1;
33
                q.push(e.to);
34
            }
35
        }
36
    }
37

38
    return level[t] >= 0;
39
}
40

41
int dfs(int u, int pushed) {
42
    if (u == t || pushed == 0) return pushed;
43

44
    for (int& i = iter[u]; i < graph[u].size(); i++) {
45
        Edge& e = graph[u][i];
46

47
        if (level[u] + 1 != level[e.to] || e.cap <= 0)
48
            continue;
49

50
        int flow = dfs(e.to, min(pushed, e.cap));
51

52
        if (flow > 0) {
53
            e.cap -= flow;
54
            graph[e.to][e.rev].cap += flow;
55
            return flow;
56
        }
57
    }
58

59
    return 0;
60
}
61

62
int edmonds_karp() {
63
    int max_flow = 0;
64

65
    while (bfs()) {
66
        memset(iter, 0, sizeof(iter));
67
        int flow;
68
        while ((flow = dfs(s, INF)) > 0) {
69
            max_flow += flow;
70
        }
71
    }
72

73
    return max_flow;
74
}

时间复杂度： $O(VE^2)$

2.3 Dinic 算法#

Dinic 算法通过构造分层图和多路增广优化效率。

关键优化：

分层图：使用BFS构造按最短路长度分层的图
当前弧优化：记录每个节点当前搜索到的边，避免重复搜索
多路增广：一次BFS后可以进行多次DFS增广

1
// Dinic算法实现（使用上面的代码结构）
2
int dinic() {
3
    int max_flow = 0;
4

5
    while (bfs()) {
6
        memset(iter, 0, sizeof(iter));
7
        int flow;
8
        while ((flow = dfs(s, INF)) > 0) {
9
            max_flow += flow;
10
        }
11
    }
12

13
    return max_flow;
14
}

时间复杂度： $O(V^2E)$ ，单位容量网络中为 $O(E\sqrt{V})$

2.4 ISAP 算法#

ISAP (Improved Shortest Augmenting Path) 通过维护距离标号和gap优化避免无效BFS。

1
int gap[MAXN], dis[MAXN], cur[MAXN];
2
int cnt[MAXN];
3

4
void init_isap() {
5
    memset(dis, 0, sizeof(dis));
6
    memset(gap, 0, sizeof(gap));
7
    memset(cnt, 0, sizeof(cnt));
8

9
    queue<int> q;
10
    q.push(t);
11
    dis[t] = 0;
12
    cnt[0] = 1;
13

14
    while (!q.empty()) {
15
        int u = q.front();
16
        q.pop();
17

18
        for (auto& e : graph[u]) {
19
            int v = e.to;
20
            if (dis[v] == 0 && v != t) {
21
                dis[v] = dis[u] + 1;
22
                cnt[dis[v]]++;
23
                q.push(v);
24
            }
25
        }
26
    }
27
}
28

29
int isap_dfs(int u, int pushed) {
30
    if (u == t) return pushed;
31

32
    int flow = 0;
33
    for (int& i = cur[u]; i < graph[u].size(); i++) {
34
        Edge& e = graph[u][i];
35

36
        if (e.cap > 0 && dis[u] == dis[e.to] + 1) {
37
            int f = isap_dfs(e.to, min(pushed - flow, e.cap));
38

39
            if (f > 0) {
40
                e.cap -= f;
41
                graph[e.to][e.rev].cap += f;
42
                flow += f;
43
                if (flow == pushed) return flow;
44
            }
45
        }
46
    }
47

48
    // Gap优化
49
    if (--cnt[dis[u]] == 0) dis[s] = n + 1;
50
    cnt[++dis[u]]++;
51
    cur[u] = 0;
52

53
    return flow;
54
}
55

56
int isap() {
57
    init_isap();
58
    int max_flow = 0;
59

60
    while (dis[s] < n) {
61
        memcpy(cur, iter, sizeof(cur));
62
        max_flow += isap_dfs(s, INF);
63
    }
64

65
    return max_flow;
66
}

时间复杂度： $O(V^2E)$

三、最小费用最大流#

最小费用最大流问题在最大流的基础上，每条边增加单位流量费用 $w(u,v)$ ，目标是在流量最大的前提下使总费用最小。

3.1 SPFA 增广#

使用SPFA算法在残量网络中寻找最小费用增广路。

1
const int MAXN = 5005;
2
const int INF = 1e9;
3

4
struct Edge {
5
    int to, cap, cost, rev;
6
};
7

8
vector<Edge> graph[MAXN];
9
int dist[MAXN], pre[MAXN], pre_edge[MAXN];
10
bool inq[MAXN];
11
int n, s, t;
12

13
void add_edge_cost(int from, int to, int cap, int cost) {
14
    graph[from].push_back({to, cap, cost, (int)graph[to].size()});
15
    graph[to].push_back({from, 0, -cost, (int)graph[from].size() - 1});
16
}
17

18
bool spfa() {
19
    fill(dist, dist + n + 1, INF);
20
    memset(inq, 0, sizeof(inq));
21

22
    queue<int> q;
23
    q.push(s);
24
    dist[s] = 0;
25
    inq[s] = true;
26

27
    while (!q.empty()) {
28
        int u = q.front();
29
        q.pop();
30
        inq[u] = false;
31

32
        for (int i = 0; i < graph[u].size(); i++) {
33
            Edge& e = graph[u][i];
34

35
            if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
36
                dist[e.to] = dist[u] + e.cost;
37
                pre[e.to] = u;
38
                pre_edge[e.to] = i;
39

40
                if (!inq[e.to]) {
41
                    q.push(e.to);
42
                    inq[e.to] = true;
43
                }
44
            }
45
        }
46
    }
47

48
    return dist[t] != INF;
49
}
50

51
pair<int, int> min_cost_max_flow() {
52
    int max_flow = 0, min_cost = 0;
53

54
    while (spfa()) {
55
        int flow = INF;
56

57
        // 找到增广路上的最小残量
58
        for (int v = t; v != s; v = pre[v]) {
59
            int u = pre[v];
60
            flow = min(flow, graph[u][pre_edge[v]].cap);
61
        }
62

63
        // 更新流量和费用
64
        for (int v = t; v != s; v = pre[v]) {
65
            int u = pre[v];
66
            int i = pre_edge[v];
67
            graph[u][i].cap -= flow;
68
            graph[v][graph[u][i].rev].cap += flow;
69
        }
70

71
        max_flow += flow;
72
        min_cost += flow * dist[t];
73
    }
74

75
    return {max_flow, min_cost};
76
}

时间复杂度： $O(nmf)$ ，其中 $f$ 是最大流

3.2 势函数优化的Dijkstra#

使用势函数 $h(v)$ 将边权变为非负，从而使用Dijkstra加速。

1
int h[MAXN];
2

3
void init_potential() {
4
    fill(h, h + n + 1, INF);
5
    h[s] = 0;
6
    queue<int> q;
7
    q.push(s);
8
    bool inq[MAXN] = {0};
9
    inq[s] = true;
10

11
    while (!q.empty()) {
12
        int u = q.front();
13
        q.pop();
14
        inq[u] = false;
15

16
        for (auto& e : graph[u]) {
17
            if (e.cap > 0 && h[e.to] > h[u] + e.cost) {
18
                h[e.to] = h[u] + e.cost;
19
                if (!inq[e.to]) {
20
                    q.push(e.to);
21
                    inq[e.to] = true;
22
                }
23
            }
24
        }
25
    }
26
}
27

28
bool dijkstra() {
29
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
30
    fill(dist, dist + n + 1, INF);
31
    dist[s] = 0;
32
    pq.push({0, s});
33

34
    while (!pq.empty()) {
35
        auto [d, u] = pq.top();
36
        pq.pop();
37

38
        if (d > dist[u]) continue;
39

40
        for (int i = 0; i < graph[u].size(); i++) {
41
            Edge& e = graph[u][i];
42
            int cost = e.cost + h[u] - h[e.to];
43

44
            if (e.cap > 0 && dist[e.to] > dist[u] + cost) {
45
                dist[e.to] = dist[u] + cost;
46
                pre[e.to] = u;
47
                pre_edge[e.to] = i;
48
                pq.push({dist[e.to], e.to});
49
            }
50
        }
51
    }
52

53
    if (dist[t] == INF) return false;
54

55
    for (int i = 0; i <= n; i++) {
56
        if (dist[i] != INF) h[i] += dist[i];
57
    }
58

59
    return true;
60
}

时间复杂度： $O(fE\log V)$

四、二分图匹配#

4.1 匈牙利算法#

二分图最大匹配的经典算法，基于交替路和增广路思想。

1
const int MAXN = 1005;
2
vector<int> g[MAXN];
3
int match[MAXN];
4
bool vis[MAXN];
5
int n, m;
6

7
bool dfs(int u) {
8
    for (int v : g[u]) {
9
        if (!vis[v]) {
10
            vis[v] = true;
11
            if (match[v] == -1 || dfs(match[v])) {
12
                match[v] = u;
13
                return true;
14
            }
15
        }
16
    }
17
    return false;
18
}
19

20
int hungarian() {
21
    memset(match, -1, sizeof(match));
22
    int ans = 0;
23

24
    for (int i = 1; i <= n; i++) {
25
        memset(vis, 0, sizeof(vis));
26
        if (dfs(i)) ans++;
27
    }
28

29
    return ans;
30
}

时间复杂度： $O(VE)$

4.2 Kuhn-Munkres (KM) 算法#

用于求解带权二分图的最大权完美匹配。

1
const int MAXN = 305;
2
const int INF = 1e9;
3

4
int w[MAXN][MAXN];
5
int lx[MAXN], ly[MAXN];
6
int match[MAXN];
7
bool visx[MAXN], visy[MAXN];
8
int slack[MAXN];
9
int n;
10

11
bool dfs_km(int u) {
12
    visx[u] = true;
13

14
    for (int v = 1; v <= n; v++) {
15
        if (visy[v]) continue;
16

17
        int gap = lx[u] + ly[v] - w[u][v];
18

19
        if (gap == 0) {
20
            visy[v] = true;
21
            if (match[v] == -1 || dfs_km(match[v])) {
22
                match[v] = u;
23
                return true;
24
            }
25
        } else {
26
            slack[v] = min(slack[v], gap);
27
        }
28
    }
29

30
    return false;
31
}
32

33
int kuhn_munkres() {
34
    memset(match, -1, sizeof(match));
35
    memset(ly, 0, sizeof(ly));
36

37
    for (int i = 1; i <= n; i++) {
38
        lx[i] = -INF;
39
        for (int j = 1; j <= n; j++) {
40
            lx[i] = max(lx[i], w[i][j]);
41
        }
42
    }
43

44
    for (int i = 1; i <= n; i++) {
45
        fill(slack + 1, slack + n + 1, INF);
46

47
        while (true) {
48
            memset(visx, 0, sizeof(visx));
49
            memset(visy, 0, sizeof(visy));
50

51
            if (dfs_km(i)) break;
52

53
            int delta = INF;
54
            for (int j = 1; j <= n; j++) {
55
                if (!visy[j]) delta = min(delta, slack[j]);
56
            }
57

58
            for (int j = 1; j <= n; j++) {
59
                if (visx[j]) lx[j] -= delta;
60
                if (visy[j]) ly[j] += delta;
61
                else slack[j] -= delta;
62
            }
63
        }
64
    }
65

66
    int ans = 0;
67
    for (int i = 1; i <= n; i++) {
68
        if (match[i] != -1) {
69
            ans += w[match[i]][i];
70
        }
71
    }
72

73
    return ans;
74
}

时间复杂度： $O(V^3)$

五、最小割与最大流定理#

5.1 最大流最小割定理#

定理：网络中最大流的值等于最小割的容量。

割 $(S,T)$ 是将顶点集 $V$ 划分为两个集合，其中 $s \in S, t \in T$ 。

割的容量： $c(S,T) = \sum_{u \in S, v \in T} c(u,v)$

证明思路：

任何流的值 $\leq$ 任何割的容量
找到一个流和一个割使得它们相等

5.2 最小割应用#

求最小割只需在最大流算法结束后，在残量网络中从源点BFS能到达的点属于 $S$ ，其余属于 $T$ 。

1
void find_min_cut(vector<int>& S, vector<int>& T) {
2
    bool vis[MAXN] = {0};
3
    queue<int> q;
4
    q.push(s);
5
    vis[s] = true;
6

7
    while (!q.empty()) {
8
        int u = q.front();
9
        q.pop();
10
        S.push_back(u);
11

12
        for (auto& e : graph[u]) {
13
            if (e.cap > 0 && !vis[e.to]) {
14
                vis[e.to] = true;
15
                q.push(e.to);
16
            }
17
        }
18
    }
19

20
    for (int i = 1; i <= n; i++) {
21
        if (!vis[i]) T.push_back(i);
22
    }
23
}

六、网络流建模技巧#

6.1 拆点技巧#

点容量限制：将点 $v$ 拆成 $v_{in}$ 和 $v_{out}$ ，连边 $(v_{in}, v_{out}, c_v)$ 。

6.2 多源多汇#

建立超级源点 $s'$ 和超级汇点 $t'$ ：

从 $s'$ 向所有源点连容量为 $\infty$ 的边
从所有汇点向 $t'$ 连容量为 $\infty$ 的边

6.3 最大权闭合子图#

问题：给定带权有向图，求权值和最大的闭合子图。

建模：

源点向所有正权点连边，容量为权值
所有负权点向汇点连边，容量为权值的绝对值
原图边容量为 $\infty$
答案 = 正权和 - 最小割

1
int max_closure(vector<int>& weight, vector<pair<int,int>>& edges) {
2
    int sum_pos = 0;
3

4
    for (int i = 0; i < weight.size(); i++) {
5
        if (weight[i] > 0) {
6
            add_edge(s, i + 1, weight[i]);
7
            sum_pos += weight[i];
8
        } else if (weight[i] < 0) {
9
            add_edge(i + 1, t, -weight[i]);
10
        }
11
    }
12

13
    for (auto [u, v] : edges) {
14
        add_edge(u + 1, v + 1, INF);
15
    }
16

17
    return sum_pos - max_flow();
18
}

七、上下界网络流#

7.1 无源汇上下界可行流#

每条边 $(u,v)$ 有流量下界 $l(u,v)$ 和上界 $r(u,v)$ 。

转化方法：

对每条边 $(u,v)$ ，强制流量至少为 $l(u,v)$
建立新图，边容量为 $r(u,v) - l(u,v)$
对每个点维护初始盈亏度： $M(v) = \sum_{u} l(u,v) - \sum_{w} l(v,w)$
建立超级源汇， $M(v) > 0$ 时从源点连边， $M(v) < 0$ 时连向汇点
求最大流，若流量等于所有从源点出发的边容量和，则存在可行流

1
int lower[MAXN][MAXN], upper[MAXN][MAXN];
2
int deg[MAXN];
3

4
bool feasible_flow() {
5
    // 建图
6
    int sum = 0;
7
    for (int u = 1; u <= n; u++) {
8
        for (int v = 1; v <= n; v++) {
9
            if (upper[u][v] > 0) {
10
                add_edge(u, v, upper[u][v] - lower[u][v]);
11
                deg[u] -= lower[u][v];
12
                deg[v] += lower[u][v];
13
            }
14
        }
15
    }
16

17
    // 超级源汇
18
    int ss = 0, tt = n + 1;
19
    for (int i = 1; i <= n; i++) {
20
        if (deg[i] > 0) {
21
            add_edge(ss, i, deg[i]);
22
            sum += deg[i];
23
        } else if (deg[i] < 0) {
24
            add_edge(i, tt, -deg[i]);
25
        }
26
    }
27

28
    s = ss; t = tt;
29
    return max_flow() == sum;
30
}

7.2 有源汇上下界最大流#

从汇点 $t$ 向源点 $s$ 连一条容量为 $\infty$ 的边
按无源汇可行流求解
删除 $t \to s$ 的边，在残量网络上从 $s$ 到 $t$ 跑最大流

7.3 有源汇上下界最小流#

求上下界最大流
在残量网络中从 $t$ 到 $s$ 跑最大流
答案 = 上下界最大流 - 反向最大流

八、费用流的应用#

8.1 最小费用最大流问题#

例题：运输问题

有 $n$ 个仓库和 $m$ 个零售商，仓库 $i$ 有 $a_i$ 个货物，零售商 $j$ 需要 $b_j$ 个货物。从仓库 $i$ 运到零售商 $j$ 的单位费用是 $c_{ij}$ 。求最小运输费用。

建模：

源点向每个仓库连边，容量 $a_i$ ，费用 0
每个零售商向汇点连边，容量 $b_j$ ，费用 0
仓库 $i$ 向零售商 $j$ 连边，容量 $\infty$ ，费用 $c_{ij}$

8.2 最大费用最大流#

将所有边的费用取反，跑最小费用最大流，结果再取反即可。

九、IOI级别综合题#

9.1 例题：最优乘车方案#

问题：城市有 $n$ 个站点和 $m$ 条公交线路。每条线路是一个站点序列，按顺序停靠。票价系统为：

乘坐一段路程（不换乘）费用为 $a$
换乘费用为 $b$

求从站点 $s$ 到站点 $t$ 的最小费用。

建模思路：

对每个站点拆点为 $u_{in}$ 和 $u_{out}$
$u_{in}$ 到 $u_{out}$ 连边，容量 1，费用 0
对同一线路上相邻站点 $u, v$ ，连边 $(u_{out}, v_{in})$ ，容量 1，费用 $a$
不同线路间换乘，若站点 $u$ 在线路 $L_1$ 和 $L_2$ 上，连边表示换乘，费用 $b$

9.2 例题：最小路径覆盖#

问题：给定DAG，用最少的不相交路径覆盖所有顶点。

建模：

拆点：每个点 $v$ 拆成 $v_L$ 和 $v_R$
每条边 $(u,v)$ 转化为 $u_L \to v_R$
源点向所有 $v_L$ 连边，所有 $v_R$ 向汇点连边
最小路径覆盖数 = $n$ - 最大匹配数

1
int min_path_cover(int n, vector<pair<int,int>>& edges) {
2
    // 建图
3
    for (auto [u, v] : edges) {
4
        add_edge(u, v + n, 1);
5
    }
6

7
    // 源汇连边
8
    for (int i = 1; i <= n; i++) {
9
        add_edge(s, i, 1);
10
        add_edge(i + n, t, 1);
11
    }
12

13
    int max_match = max_flow();
14
    return n - max_match;
15
}

9.3 例题：餐巾计划问题#

问题：餐厅 $n$ 天运营，第 $i$ 天需要 $r_i$ 条干净餐巾。有以下选择：

购买新餐巾，单价 $p$
快洗： $m$ 天后可用，费用 $f$
慢洗： $n$ 天后可用，费用 $s$

求最小费用方案。

建模：

拆点：每天拆成白天和晚上节点
白天需求从源点流入，容量 $r_i$ ，费用 0
晚上脏餐巾流向汇点
购买：源点到白天节点，容量 $\infty$ ，费用 $p$
快洗：晚上节点向 $m$ 天后白天节点连边，费用 $f$
慢洗：晚上节点向 $n$ 天后白天节点连边，费用 $s$
相邻天数脏餐巾转移边

十、复杂度总结与选择#

算法	时间复杂度	适用场景
Edmonds-Karp	$O(VE^2)$	小规模，代码简单
Dinic	$O(V^2E)$	一般图，单位网络 $O(E\sqrt{V})$
ISAP	$O(V^2E)$	稠密图，常数小
匈牙利	$O(VE)$	二分图匹配
KM	$O(V^3)$	带权匹配
MCMF (SPFA)	$O(nmf)$	小流量
MCMF (Dijkstra)	$O(fE\log V)$	大流量

选择建议：

CSP-S/NOI：掌握Dinic + 匈牙利 + SPFA费用流
IOI/ICPC：Dinic + Dijkstra费用流 + 各类建模
工程应用：根据数据规模选择，注意常数优化

总结#

网络流是算法竞赛中的核心内容，需要：

理论基础：理解增广路、残量网络等概念
算法实现：熟练编写Dinic、费用流、匈牙利算法
建模能力：识别问题，转化为网络流模型
优化技巧：根据数据特点选择合适算法

掌握网络流不仅能解决图论问题，更能培养建模思维和优化意识，是从CSP-S走向IOI的必经之路。

推荐练习：

洛谷 P3376 最大流模板
洛谷 P3381 最小费用最大流模板
POJ 1273, 1274, 2195
Codeforces 网络流专题

祝各位在算法竞赛的道路上不断进步！