网络流学习笔记

不想说话真君 · 2026-08-15 17:20:17 · 算法·理论

本文使用老师同学以及人工智能进行润色，保证我的贡献严格大于他们的贡献。

一、一些概念

1.1 定义

一个流网络 G=(V,E) 是一个有向图，满足以下条件：

• 图中有一个特殊的顶点 s，称为源点，它只有出边没有入边
• 图中有一个特殊的顶点 t，称为汇点，它只有入边没有出边
• 每条边 e \in E 都有一个非负实数 c_e，称为该边的容量，表示该边单位时间内最大可通过的流量

1.2 注意事项

• 容量 c_e \ge 0，可以为 0（表示该边不可通过）
• 一般假设图中没有自环（u \to u 的边）
• 如果存在重边，可以合并为一条边，容量相加
• 源点 s 和汇点 t 是不同的顶点

二、流

2.1 定义

流网络 G=(V,E) 上的一个流是一个从边集到非负实数的映射，它必须满足以下两个条件：

1. 对每条边 e \in E，都有：

即每条边上的流量不得超过其容量。流量不能为负，表示物质不能逆流。

2. 对每个中间顶点 u \in V \set \min us \{s,t\}，都有：

其中 \text{in}(u) 表示指向 u 的边集，\text{out}(u) 表示从 u 出发的边集。

说人话就是流入该点的总流量等于流出该点的总流量。也称为能量守恒。

2.2 流值

流的流值定义为从源点流出的总流量：

如果源点没有入边（或约定不计入），则简化为：

根据流量守恒，流值也等于流入汇点的总流量：

可以把图化为水管：

• 容量是管道的最大输水能力
• 流量是管道中实际流过的水量
• 流量守恒表示中间节点既不储存水也不凭空产生水
• 流值是单位时间从源点发出的总水量

2.3 零流与满流

• 零流：所有边的流量都为 0 的流，即 f_e = 0 对所有 e \in E 成立，此时 |f|=0
• 满流：所有边的流量都等于其容量的流，即 f_e = c_e 对所有 e \in E 成立（注意满流不一定存在）

三、最大流问题

3.1 问题定义

我理解这个定义花了一个晚上，最简单最直接最不绕弯子的定义表述：源点有 x 的水量，通过多次水管运输且单个水管运输量不超过水管容量的情况下能将 x 的水全部运输到汇点的最大的满足要求的 x。

四、残量网络

4.1 残量

对于流网络 G 上的流 f，定义每条边 e=(u,v) 的残量为：

残量表示该边还能通过多少流量。

4.2 残量网络

残量网络 G_f 是一个基于原网络和当前流构造的新网络：

• 对原网络中每条边 e=(u,v)，若 c_e - f_e > 0（残量大于 0），则在 G_f 中保留一条边 u \to v，容量为 c_e - f_e，称为正向边。
• 同时引入一条反向边 v \to u，容量为 f_e，表示可以 "撤销" 之前流过的流量。

4.3 反向边的意义

反向边是网络流中一个非常巧妙的设计：

• 它允许算法 "后悔"—— 撤销之前的不当决策
• 当沿 u \to v 推送了流量 d 后，正向边残量减少 d，反向边残量增加 d。
• 如果后来发现沿某条路径 v \to u 推送流量更优，可以通过反向边 v \to u 撤销之前的流量。

想象一条管道 u \to v 已经流了 5 单位流量。反向边 v \to u 的容量为 5，表示 " 可以从 v 端抽回 5 单位流量 "，这相当于让 u \to v 少流 5。

4.4 残量网络的性质

• 残量网络中每条边都有正容量
• 残量网络可能包含原网络中没有的边（反向边）
• 一个流是最大流当且仅当残量网络中不存在从 s 到 t 的路径

五、增广路与增广

5.1 增广路

增广路是残量网络 G_f 中从源点 s 到汇点 t 的一条简单路径，路径上每条边的残量都大于 0。

5.2 增广

增广是沿增广路推送流量的过程：

1. 找到增广路 P，计算路径上最小残量：

2. 对路径上每条边：

   • 若是正向边 e=(u,v)：f_e \gets f_e + \Delta（增加流量）
   • 若是反向边 e=(v,u)：f_{(u,v)} \gets f_{(u,v)} - \Delta（撤销流量）

3. 流值增加 \Delta：|f| \gets |f| + \Delta

5.3 增广路定理

增广路定理：

一个流 f 是最大流当且仅当其残量网络 G_f 中不存在从 s 到 t 的增广路。

这给出了求最大流的基本思路：不断找增广路并增广，直到找不到为止。

六、最大流最小割

6.1 割

流网络 G=(V,E) 的一个割是将顶点集 V 分为两部分 S 和 T=V \set \min us S，满足 s \in S，t \in T。

6.2 割的容量

割 (S,T) 的容量定义为从 S 指向 T 的所有边的容量之和：

注意：只计算从 S 到 T 的边，不计算从 T 到 S 的边。

6.3 割的流量

割 (S,T) 的流量定义为：

即从 S 流向 T 的总流量减去从 T 流向 S 的总流量。

6.4 流值与割的关系

对任意割 (S,T)，都有：

即流值等于任意割的净流量。这是由流量守恒推导得到的。

6.5 割的容量下界

对任意流 f 和任意割 (S,T)，都有：

即流值不超过任意割的容量。这给出了最大流的一个上界。

6.6 最小割

最小割问题是求所有割中容量最小的割：

6.7 最大流最小割定理

最大流最小割定理：

即最大流等于最小割。

算法

EK 算法

这个算法比较简单，每次找到一条增广路（第 5 章会讲是什么）然后将这条增广路加上增广路的最小边剩余容量，一直找直到找不到为止，答案就是找到的所有增广路的最小边剩余容量之和。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, s, t;
vector<pair<pair<int, int>, int>> vec[10005];
int vis[10005];
struct edge
{
    int v1, w1, id;
} pre[10005];
bool bfs()
{
    queue<int> que;
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    que.push(s);
    while (!que.empty())
    {
        int v = que.front();
        que.pop();
        if (v == t)
            return 1;
        for (int i = 1; i < vec[v].size(); i++)
        {
            if (vec[v][i].first.second && !vis[vec[v][i].first.first])
            {
                vis[vec[v][i].first.first] = 1;
                pre[vec[v][i].first.first].v1 = v;
                pre[vec[v][i].first.first].w1 = vec[v][i].first.second;
                pre[vec[v][i].first.first].id = i;
                que.push(vec[v][i].first.first);
            }
        }
    }
    return 0;
}
signed main()
{
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i++)
    {
        vec[i].push_back({{0, 0}, 0});
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        vec[u].push_back({{v, w}, vec[v].size()});
        vec[v].push_back({{u, 0}, vec[u].size() - 1});
    }
    int ans = 0;
    while (bfs())
    {
        int minn = 1e18;
        for (int i = t; i != s; i = pre[i].v1)
        {
            minn = min(minn, pre[i].w1);
        }
        for (int i = t; i != s; i = pre[i].v1)
        {
            vec[pre[i].v1][pre[i].id].first.second -= minn;
            vec[i][vec[pre[i].v1][pre[i].id].second].first.second += minn;
        }
        ans += minn;
    }
    cout << ans << endl;
}

复杂度：O(nm^2)，但是远达不到。

模板题是 P3376。

dinic 算法

EK 算法还是太不牛了，一次只能找一个增广路，有没有什么算法一次找多个？

有的兄弟有的，Dinic 算法。

Dinic 算法利用了分层图。

在残量网络中，从源点 s 做 BFS，记录每个点 u 到 s 的最短距离 d_u（只走残量大于 0 的边）。这样把网络分为若干层：

• 第 0 层：s（d_s=0）
• 第 i 层：所有 d_u=i 的点

分层图只保留满足 d_v = d_u+1 的边 u \to v，即只走往下一层的边。

Dinic 在每个阶段只找最短的增广路，使得：

• 每个阶段所有增广路长度相同
• 一个阶段结束后，最短增广路长度必然增加
• 最短增广路长度最多增加 n-1 次，故最多 n 个阶段

复杂度 O(n^2m)，与 EK 算法相同的：远达不到。

代码：

#include <bits/stdc++.h>
using namespace std;
#define add(u, v, w)                           \
    vec[u].push_back({{v, w}, vec[v].size()}); \
    vec[v].push_back({{u, 0}, vec[u].size() - 1});
#define int long long
int n, m, s, t, L;
vector<pair<pair<int, int>, int>> vec[41000];
int de[41000], cu[41000], q[41000];
bool bfs()
{
    for (int i = 0; i <= t; i++)
        de[i] = 0;
    int he = 0, ta = 0;
    q[ta++] = s;
    de[s] = 1;
    while (he < ta)
    {
        int v = q[he++];
        for (int i = 0; i < (int)vec[v].size(); i++)
        {
            int to = vec[v][i].first.first;
            int ca = vec[v][i].first.second;
            if (ca && !de[to])
            {
                de[to] = de[v] + 1;
                q[ta++] = to;
            }
        }
    }
    return de[t] != 0;
}
int dfs(int v, int fl)
{
    if (v == t)
        return fl;
    int re = 0;
    for (int &i = cu[v]; i < (int)vec[v].size(); i++)
    {
        int to = vec[v][i].first.first;
        int ca = vec[v][i].first.second;
        if (ca && de[to] == de[v] + 1)
        {
            int d = dfs(to, min(fl - re, ca));
            if (d > 0)
            {
                vec[v][i].first.second -= d;
                vec[to][vec[v][i].second].first.second += d;
                re += d;
                if (re == fl)
                    return re;
            }
        }
    }
    return re;
}
int dinic()
{
    int f = 0;
    while (bfs())
    {
        for (int i = 0; i <= t; i++)
            cu[i] = 0;
        int d;
        while ((d = dfs(s, 1e18)) != 0)
        {
            f += d;
        }
    }
    return f;
}
signed main()
{
}

例题

这里会选一些老师让我们做的题目。

试题库问题

题意

大概就是 n 个题目好几个标签 b_i，现在需要第 i 个标签 a_i 个。

思路

一个题目能为一种标签贡献 1，把源点对每个题目连一条容量为 1 的边，每个题目对其拥有的标签连一条容量为 1 的边，如果这条边的流是 1 代表这个题目选了这个标签，否则就是不选，然后每个标签对汇点连一条容量为 a_i 的边表示需要 a_i 个这种标签。

对这个图跑一下最大流，若最大流不是 \sum_{i=1}^n a_i，无解，否则，对于每个标签，枚举哪些题目指向了它，输出即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, s, t;
vector<pair<pair<int, int>, int>> vec[10005];
int vis[10005];
struct edge
{
    int v1, w1, id;
} pre[10005];
bool bfs()
{
    queue<int> que;
    memset(vis, 0, sizeof(vis));
    vis[s] = 1;
    que.push(s);
    while (!que.empty())
    {
        int v = que.front();
        que.pop();
        if (v == t)
            return 1;
        for (int i = 1; i < vec[v].size(); i++)
        {
            if (vec[v][i].first.second && !vis[vec[v][i].first.first])
            {
                vis[vec[v][i].first.first] = 1;
                pre[vec[v][i].first.first].v1 = v;
                pre[vec[v][i].first.first].w1 = vec[v][i].first.second;
                pre[vec[v][i].first.first].id = i;
                que.push(vec[v][i].first.first);
            }
        }
    }
    return 0;
}
signed main()
{
    volatile char c1;
    clock_t b = clock();
    cin >> n >> m;
    int sum = 0;
    s = 0;
    t = n + m + 1;
    for (int i = 0; i <= t; i++)
        vec[i].push_back({{0, 0}, 0});
    for (int i = 1; i <= n; i++)
    {
        int w;
        cin >> w;
        sum += w;
        vec[s].push_back({{i, w}, vec[i].size()});
        vec[i].push_back({{s, 0}, vec[s].size() - 1});
    }
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        int q = n + i;
        vec[q].push_back({{t, 1}, vec[t].size()});
        vec[t].push_back({{q, 0}, vec[q].size() - 1});
        for (int j = 1; j <= x; j++)
        {
            int u;
            cin >> u;
            vec[u].push_back({{q, 1}, vec[q].size()});
            vec[q].push_back({{u, 0}, vec[u].size() - 1});
        }
    }
    int ans = 0;
    while (bfs())
    {
        int minn = 1e18;
        for (int i = t; i != s; i = pre[i].v1)
            minn = min(minn, pre[i].w1);
        for (int i = t; i != s; i = pre[i].v1)
        {
            vec[pre[i].v1][pre[i].id].first.second -= minn;
            vec[i][vec[pre[i].v1][pre[i].id].second].first.second += minn;
        }
        ans += minn;
    }
    if (ans != sum)
        cout << "No Solution!" << endl;
    else
    {
        for (int i = 1; i <= n; i++)
        {
            cout << i << ":";
            for (int j = 1; j < vec[i].size(); j++)
                if (vec[i][j].first.second == 0 && vec[i][j].first.first > n && vec[i][j].first.first <= n + m)
                    cout << " " << vec[i][j].first.first - n;
            cout << endl;
        }
    }
    volatile char c2;
    cerr << "Memory: " << abs(&c1 - &c2) / 1024 / 1024 << " MB" << endl;
    clock_t e = clock();
    cerr << "Time: " << (double)(e - b) * 1000 / CLOCKS_PER_SEC << " ms" << endl;
}

[POI 2005] KOS-Dicing

题意