网络流初步认识

YZY Lv3
  2025-07-02 02:18:38 2025-07-02 02:18:38 Created   2025-07-02 02:18:38 2025-07-02 02:18:38 Updated      

1. 图的构成

网络流问题通常在一个有向图中求解，这个图由以下几个部分构成：

  • 节点（Vertex）：表示网络中的不同点，如城市、站点等。
  • 边（Edge）：表示连接两个节点的路径，每条边有一个容量，即该边能够传输的最大流量。
  • 源点（Source）：流量的起始节点，通常标记为 S。
  • 汇点（Sink）：流量的终点节点，通常标记为 T。

2. 流量和容量

  • 流量（Flow）：从源点到汇点传递的“物品”或“信息”，每条边上的流量必须满足一定的限制。
  • 容量（Capacity）：每条边的最大流量限制，也就是该边最多能够传递的流量。容量通常是一个正整数。
  • 流量守恒（Flow Conservation）：对于每个节点，进入该节点的流量必须等于从该节点流出的流量，除了源点和汇点。

3. 最大流问题

最大流问题的目标是找到从源点到汇点的最大流量，即在网络中尽可能多地传递流量，而不超过边的容量。通过算法计算得到最大流，可以用来解决如网络传输、交通调度等问题。

4. 最小割定理

  • 最小割（Minimum Cut）：在网络流问题中，割是指将图的节点分为两部分，其中一部分包含源点，另一部分包含汇点。最小割是使得从源点到汇点的所有流量被切断的边的总容量最小。
  • 最小割定理：最大流等于最小割的容量。这个定理是求解最大流问题的理论基础。

5. 常见算法

为了求解网络流问题，常用的算法包括：

  • Ford-Fulkerson 算法：一种基于增广路径（Augmenting Path）的算法，通过不断找到可以增加流量的路径来增加流量，直到无法找到增广路径为止。
  • Edmonds-Karp 算法：Ford-Fulkerson 算法的一个实现，使用广度优先搜索（BFS）寻找增广路径，确保算法在多项式时间内完成。
  • Dinic 算法：一个优化的最大流算法，使用分层图来加速增广路径的搜索。

经典算法

1. Ford-Fulkerson算法

Ford-Fulkerson算法基于增广路径的思想，逐步增加从源点到汇点的流量，直到无法找到增广路径为止。

基本思路：

  • 从源点出发，使用深度优先搜索（DFS）或广度优先搜索（BFS）寻找一条增广路径（即未满流的路径）。
  • 找到增广路径后，计算路径上的最小容量，并更新路径上每条边的流量。
  • 重复上述过程，直到无法找到增广路径为止。

代码模板：

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1000;  // 最大节点数
const int INF = 1e9;     // 无限大

int n, m;                // n是节点数，m是边数
vector<int> adj[MAXN];   // 邻接表
int capacity[MAXN][MAXN]; // 容量矩阵
int flow[MAXN][MAXN];     // 流量矩阵

// 寻找增广路径的DFS
bool dfs(int u, int t, int f, vector<int>& visited) {
    if (u == t) return true;
    visited[u] = 1;
    for (int v : adj[u]) {
        if (!visited[v] && capacity[u][v] > flow[u][v]) {
            if (dfs(v, t, min(f, capacity[u][v] - flow[u][v]), visited)) {
                flow[u][v] += f;
                flow[v][u] -= f;
                return true;
            }
        }
    }
    return false;
}

// 最大流计算
int fordFulkerson(int source, int sink) {
    memset(flow, 0, sizeof(flow)); // 初始化流量矩阵
    int maxFlow = 0;

    while (true) {
        vector<int> visited(n, 0);
        int f = 0;
        if (!dfs(source, sink, INF, visited)) break;  // 如果没有增广路径，结束
        maxFlow += f;
    }
    return maxFlow;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back(v);
        adj[v].push_back(u);
        capacity[u][v] += c;  // 有可能是多条边，容量累加
    }
    cout << fordFulkerson(0, n-1) << endl;  // 假设源点是0，汇点是n-1
    return 0;
}

2. Edmonds-Karp算法

Edmonds-Karp算法是Ford-Fulkerson算法的实现之一，使用**广度优先搜索（BFS）**来寻找增广路径，从而保证每次找到的增广路径的长度最短，时间复杂度为O(VE²)。

代码模板：

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1000;  // 最大节点数
const int INF = 1e9;     // 无限大

int n, m;                // n是节点数，m是边数
vector<int> adj[MAXN];   // 邻接表
int capacity[MAXN][MAXN]; // 容量矩阵
int flow[MAXN][MAXN];     // 流量矩阵

// 使用BFS寻找增广路径
bool bfs(int source, int sink, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);  // 重置父节点
    parent[source] = source;
    queue<int> q;
    q.push(source);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (parent[v] == -1 && capacity[u][v] > flow[u][v]) {
                parent[v] = u;
                if (v == sink) return true;
                q.push(v);
            }
        }
    }
    return false;
}

// 最大流计算
int edmondsKarp(int source, int sink) {
    memset(flow, 0, sizeof(flow)); // 初始化流量矩阵
    int maxFlow = 0;
    vector<int> parent(n);

    while (bfs(source, sink, parent)) {
        int pathFlow = INF;
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = min(pathFlow, capacity[u][v] - flow[u][v]);
        }

        // 更新流量
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            flow[u][v] += pathFlow;
            flow[v][u] -= pathFlow;
        }

        maxFlow += pathFlow;
    }
    return maxFlow;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back(v);
        adj[v].push_back(u);
        capacity[u][v] += c;  // 有可能是多条边，容量累加
    }
    cout << edmondsKarp(0, n-1) << endl;  // 假设源点是0，汇点是n-1
    return 0;
}

3. Dinic算法

Dinic算法是一种更高效的最大流算法，采用分层图和增广路径分批增广的策略。其时间复杂度为O(V²E)，比Edmonds-Karp更快，特别在稠密图中表现优异。

代码模板：

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1000;  // 最大节点数
const int INF = 1e9;     // 无限大

int n, m;                // n是节点数，m是边数
vector<int> adj[MAXN];   // 邻接表
int capacity[MAXN][MAXN]; // 容量矩阵
int flow[MAXN][MAXN];     // 流量矩阵
int level[MAXN];          // 层次图

// BFS用于构建分层图
bool bfs(int source, int sink) {
    memset(level, -1, sizeof(level));  // 初始化层次图
    level[source] = 0;
    queue<int> q;
    q.push(source);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (level[v] == -1 && capacity[u][v] > flow[u][v]) {
                level[v] = level[u] + 1;
                if (v == sink) return true;
                q.push(v);
            }
        }
    }
    return false;
}

// DFS用于增广路径的寻找
int dfs(int u, int sink, int f) {
    if (u == sink) return f;
    for (int v : adj[u]) {
        if (level[v] == level[u] + 1 && capacity[u][v] > flow[u][v]) {
            int pathFlow = min(f, capacity[u][v] - flow[u][v]);
            int pushed = dfs(v, sink, pathFlow);
            if (pushed) {
                flow[u][v] += pushed;
                flow[v][u] -= pushed;
                return pushed;
            }
        }
    }
    return 0;
}

// 最大流计算
int dinic(int source, int sink) {
    memset(flow, 0, sizeof(flow));  // 初始化流量矩阵
    int maxFlow = 0;

    while (bfs(source, sink)) {
        while (true) {
            int pushed = dfs(source, sink, INF);
            if (pushed == 0) break;
            maxFlow += pushed;
        }
    }
    return maxFlow;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back(v);
        adj[v].push_back(u);
        capacity[u][v] += c;  // 有可能是多条边，容量累加
    }
    cout << dinic(0, n-1) << endl;  // 假设源点是0，汇点是n-1
    return 0;
}
  • Ford-Fulkerson 通过递归的DFS查找增广路径，时间复杂度较高，适用于较小规模的问题。
  • Edmonds-Karp 使用BFS查找增广路径，保证每次增广路径的最小长度，时间复杂度O(VE²)。
  • Dinic 算法通过分层图和批量增广路径提升效率，适用于更大规模的网络流问题。
  • Title: 网络流初步认识
  • Author: YZY
  • Created at : 2025-07-02 02:18:38
  • Updated at : 2025-07-02 02:18:38
  • Link: https://blog.dtoj.team/2025/07/02/网络流初步认识/
  • License: 三金家的Y同学
On this page
网络流初步认识
  1. 1. 图的构成
  2. 2. 流量和容量
  3. 3. 最大流问题
  4. 4. 最小割定理
  5. 5. 常见算法
  • 经典算法
    1. 1. Ford-Fulkerson算法
    2. 2. Edmonds-Karp算法
    3. 3. Dinic算法