最大流最小割 - Maximum Flow Minimum Cut

• 最大流
• 最小割
• 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 维护最短路径，这是因为网络图会有环路，并不能做到入队顺序即层次访问顺序。

#include <bits/stdc++.h>
using namespace std;
const int inf = INT_MAX;
const int S = 0;
const int T = 7;
int main() {
  vector<vector<int>> adjMat = {//         S  A  B  C  D  E  F  T
                                /* 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}};
  bool flag = true;
  while (flag) {
    cout << "-----------------------" << endl;
    for (int i = S; i <= T; i++) {
      for (int j = S; j <= T; j++) cout << adjMat[i][j] << " ";
      cout << endl;
    }
    cout << "-----------------------" << endl;
    queue<int> q;
    vector<int> prev(adjMat.size(), -1);
    vector<int> flow(adjMat.size(), 0);
    vector<int> dis(adjMat.size(), inf);
    q.push(S);
    dis[S] = 0;
    flag = false;
    while (q.size()) {
      auto v = q.front();
      q.pop();
      if (prev[v] != -1)
        flow[v] = min(flow[prev[v]], adjMat[prev[v]][v]);
      else
        flow[v] = inf;
      if (v == T) {
        int min_cap = flow[v];
        int p = v;
        cout << v << " ";
        while (prev[p] != -1) {
          cout << prev[p] << " ";
          adjMat[prev[p]][p] -= min_cap;
          adjMat[p][prev[p]] += min_cap;
          p = prev[p];
        }
        cout << "- min_cap: " << min_cap << endl;
        flag = true;
        break;
      } else {
        for (int i = S; i <= T; i++) {
          if (dis[i] > 1 + dis[v] && !flow[i] && adjMat[v][i] > 0) {
            dis[i] = 1 + dis[v];
            prev[i] = v;
            q.push(i);
          }
        }
      }
    }
  }
  int f_max = 0;
  for (int i = S; i <= T; i++) {
    f_max += adjMat[T][i];
  }
  cout << f_max << endl;
  return 0;
}