图算法整理（二）：最大流

Posted on | Edited on | In |

Ford-Fulkerson Algorithm

算法

1
2
3
4
5
6
# Gr: residual graph; G: original graph
Gr = G
flow = 0
while find a path in Gr:
    augment = min(segments in path)
    flow += augment

复杂度

$O(FE)$
F: 最大流
E: 边数

实现

参考：https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

示例图：

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool findPath(vector<vector<int>> &G, int src, int dst, vector<int> &parent) {
    vector<bool> visited(G.size(), false);
    queue<int> q;
    q.push(src);
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        visited[curr] = true;
        for (int i = 0; i < G.size(); ++i) {
            if (G[curr][i] > 0 && !visited[i]) {
                q.push(i);
                parent[i] = curr;
                visited[i] = true;
            }
        }
    }
    return visited[dst];
}
int main() {
    vector<vector<int>> G = {
            {0, 16, 13, 0,  0,  0},
            {0, 0,  10, 12, 0,  0},
            {0, 4,  0,  0,  14, 0},
            {0, 0,  9,  0,  0,  20},
            {0, 0,  0,  7,  0,  4},
            {0, 0,  0,  0,  0,  0}
    };
    int res = 0;
    vector<int> parent(G.size());
    int start = 0, end = 5;
    while (findPath(G, start, end, parent)) {
        int minFlow = INT_MAX;
        for (int i = end; i != start; i = parent[i]) {
            minFlow = min(G[parent[i]][i], minFlow);
        }
        for (int i = end; i != start; i = parent[i]) {
            G[parent[i]][i] -= minFlow;
            G[i][parent[i]] += minFlow;
        }
        res += minFlow;
    }
    cout << res << endl;
    return 0;
}

注意点：

parent数组的使用！BFS不像DFS可以记录一条路径，回退重新延伸，不过可以逆向思维，记录parent，这样倒着推也可以得到整条路径！！！