最大流最小割 - Maximum Flow Minimum Cut

Posted on Edited on In , Views: Word count in article: 633 Reading time ≈ 2 mins.
  • 最大流
  • 最小割
  • Ford-Fulkerson (Edmonds–Karp)

定义

网络 是一种特殊的有向图，包含源点 (Source) 和汇点 (Sink) ，以及容量

  • 对于 中的每条边 有其容量 (capacity) 和流量 (flow)
  • 中两个特殊的点，
  • 流经每条边的流量不大于其容量
  • 除源汇点，其余点净流量为

最大流与最小割定理

从源点到汇点的最大流量成为最大流，使割中容量最小的一个割称为最小割

可以证明，对于任意网络 ，其上的最大流 和最小割 总满足

最大流算法 (Edmonds–Karp)

原理

Edmonds–Karp 是 Ford-Fulkerson 增广的一种实现

称边 上的容量与流量之差为剩余流量 (Residual Capacity) 即

我们将 中所有节点和剩余流量大于 的边构成的子图称为残量网络 (Residual Graph)，其中

上一条从 到 的路径称为增广路 (Augmenting Path)，对于每一条增广路，我们给每一条边都加上等量的流量，以令 的流量增加，称为增广 (Augment)。因此最大流的求解可以分解为每一次在增广路上增加流量的叠加

此外，在增广过程中，我们对于每一条边 ，我们增加反向边 ，约定 ，这一性质使得我们得以退流，以找到最优解

对于每一次增广过程，我们使用 BFS 即可找到一条从 到 的增广路，直到我们找不到增广路，则说明已经获得了最大流

实现

这个 EK 算法的实现，与描述略微不同，这里的 BFS 事实上更像 Dijkstra，使用了 dis 维护最短路径，这是因为网络图会有环路，并不能做到入队顺序即层次访问顺序。

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
pair<vector<vector<int>>, int> maxFlow(vector<vector<int>> adjMat, size_t s,
                                       size_t t) {
  auto residualMat = adjMat;
  bool flag = true;

  while (flag) {
    queue<size_t> q;
    vector<size_t> prev(residualMat.size(), adjMat.size() + 1);
    vector<int> flow(residualMat.size(), 0);
    vector<int> dis(residualMat.size(), inf);
    q.push(s);
    dis[s] = 0;
    flag = false;

    while (!q.empty()) {
      auto v = q.front();
      q.pop();

      if (prev[v] != adjMat.size() + 1)
        flow[v] = min(flow[prev[v]], residualMat[prev[v]][v]);
      else
        flow[v] = inf;

      if (v == t) {
        int min_cap = flow[v];
        size_t p = v;
        while (prev[p] != adjMat.size() + 1) {
          residualMat[prev[p]][p] -= min_cap;
          residualMat[p][prev[p]] += min_cap;
          p = prev[p];
        }
        flag = true;
        break;
      } else {
        for (size_t i = 0; i < adjMat.size(); i++) {
          if (dis[i] > 1 + dis[v] && !flow[i] && residualMat[v][i] > 0) {
            dis[i] = 1 + dis[v];
            prev[i] = v;
            q.push(i);
          }
        }
      }
    }
  }

  size_t f_max = 0;

  for (size_t i = 0; i < adjMat.size(); i++) {
    f_max += residualMat[t][i];
  }

  return {residualMat, f_max};
}

最小割算法

原理

由取得最大流之后，在残量网络中 和 已经分离，我们令 能够访问到的节点集为 ，无法访问到的节点集则为 ，最小割即为

具体来说我们遍历 中节点 ， 中节点 ，我们找到所有有向边 ，即为割边的集合

实现

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
set<pair<size_t, size_t>> minCut(vector<vector<int>> residualMat,
                                 vector<vector<int>> adjMat, int s, int t) {
  queue<size_t> q;
  vector<bool> vis(residualMat.size(), false);
  q.push(s);

  while (!q.empty()) {
    auto v = q.front();
    q.pop();
    vis[v] = true;
    for (size_t i = 0; i < residualMat.size(); i++) {
      if (residualMat[v][i] && !vis[i]) {
        q.push(i);
      }
    }
  }

  set<size_t> S;
  set<size_t> T;
  for (size_t i = 0; i < adjMat.size(); i++) {
    if (vis[i])
      S.emplace(i);
    else
      T.emplace(i);
  }

  assert(S.count(s));
  assert(T.count(t));

  set<pair<size_t, size_t>> min_cut;

  for (auto u : S)
    for (auto v : T)
      if (adjMat[u][v]) min_cut.emplace(u, v);

  return min_cut;
}

完整Demo

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
113
114
115
#include <bits/stdc++.h>
using namespace std;
const int inf = INT_MAX;
pair<vector<vector<int>>, int> maxFlow(vector<vector<int>> adjMat, size_t s,
                                       size_t t) {
  auto residualMat = adjMat;
  bool flag = true;
  while (flag) {
    cout << "-----------------------" << endl;
    for (size_t i = 0; i < residualMat.size(); i++) {
      for (size_t j = 0; j < residualMat.size(); j++)
        cout << residualMat[i][j] << " ";
      cout << endl;
    }
    cout << "-----------------------" << endl;
    queue<size_t> q;
    vector<size_t> prev(residualMat.size(), adjMat.size() + 1);
    vector<int> flow(residualMat.size(), 0);
    vector<int> dis(residualMat.size(), inf);
    q.push(s);
    dis[s] = 0;
    flag = false;
    while (!q.empty()) {
      auto v = q.front();
      q.pop();
      if (prev[v] != adjMat.size() + 1)
        flow[v] = min(flow[prev[v]], residualMat[prev[v]][v]);
      else
        flow[v] = inf;
      if (v == t) {
        int min_cap = flow[v];
        size_t p = v;
        cout << v << " ";
        while (prev[p] != adjMat.size() + 1) {
          cout << prev[p] << " ";
          residualMat[prev[p]][p] -= min_cap;
          residualMat[p][prev[p]] += min_cap;
          p = prev[p];
        }
        cout << "- min_cap: " << min_cap << endl;
        flag = true;
        break;
      } else {
        for (size_t i = 0; i < adjMat.size(); i++) {
          if (dis[i] > 1 + dis[v] && !flow[i] && residualMat[v][i] > 0) {
            dis[i] = 1 + dis[v];
            prev[i] = v;
            q.push(i);
          }
        }
      }
    }
  }
  size_t f_max = 0;
  for (size_t i = 0; i < adjMat.size(); i++) {
    f_max += residualMat[t][i];
  }

  return {residualMat, f_max};
}

set<pair<size_t, size_t>> minCut(vector<vector<int>> residualMat,
                                 vector<vector<int>> adjMat, int s, int t) {
  queue<size_t> q;
  vector<bool> vis(residualMat.size(), false);
  q.push(s);
  while (!q.empty()) {
    auto v = q.front();
    q.pop();
    vis[v] = true;
    for (size_t i = 0; i < residualMat.size(); i++) {
      if (residualMat[v][i] && !vis[i]) {
        q.push(i);
      }
    }
  }

  set<size_t> S;
  set<size_t> T;
  for (size_t i = 0; i < adjMat.size(); i++) {
    if (vis[i])
      S.emplace(i);
    else
      T.emplace(i);
  }

  assert(S.count(s));
  assert(T.count(t));
  set<pair<size_t, size_t>> min_cut;

  for (auto u : S)
    for (auto v : T)
      if (adjMat[u][v]) min_cut.emplace(u, v);
  return min_cut;
}

int main() {
  vector<vector<int>> adjMat = {//         S  A  B  C  D  E  F  T
                                //         0  1  2  3  4  5  6  7
                                /* S 0 */ {0, 8, 7, 4, 0, 0, 0, 0},
                                /* A 1 */ {0, 0, 2, 0, 3, 9, 0, 0},
                                /* B 2 */ {0, 0, 0, 5, 0, 6, 0, 0},
                                /* C 3 */ {0, 0, 0, 0, 0, 7, 2, 0},
                                /* D 4 */ {0, 0, 0, 0, 0, 0, 0, 9},
                                /* E 5 */ {0, 0, 0, 0, 3, 0, 4, 5},
                                /* F 6 */ {0, 0, 0, 0, 0, 0, 0, 8},
                                /* T 7 */ {0, 0, 0, 0, 0, 0, 0, 0}};
  auto [residualMat, f_max] = maxFlow(adjMat, 0, 7);
  auto min_cut = minCut(residualMat, adjMat, 0, 7);
  for (auto pr : min_cut) {
    cout << "(" << pr.first << ", " << pr.second << ")" << endl;
  }
  cout << f_max << endl;
  return 0;
}