最大流

本页面主要介绍最大流问题相关的算法知识。

概述

网络流基本概念参见 网络流简介。

令 是一个有源汇点的网络，我们希望在 上指定合适的流 ，以最大化整个网络的流量 （即 ），这一问题被称作最大流问题（Maximum flow problem）。

Ford–Fulkerson 增广

Ford–Fulkerson 增广是计算最大流的一类算法的总称。该方法运用贪心的思想，通过寻找增广路来更新并求解最大流。

概述

给定网络 及 上的流 ，我们做如下定义。

对于边 ，我们将其容量与流量之差称为剩余容量 （Residual Capacity），即 。

我们将 中所有结点和剩余容量大于 的边构成的子图称为残量网络 （Residual Network），即 ，其中 。

我们将 上一条从源点 到汇点 的路径称为增广路（Augmenting Path）。对于一条增广路，我们给每一条边 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广（Augment）。由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。

此外，在 Ford–Fulkerson 增广的过程中，对于每条边 ，我们都新建一条反向边 。我们约定 ，这一性质可以通过在每次增广时引入退流操作来保证，即 增加时 应当减少同等的量。

初次接触这一方法的读者可能察觉到一个违反直觉的情形——反向边的流量 可能是一个负值。实际上我们可以注意到，在 Ford–Fulkerson 增广的过程中，真正有意义的是剩余容量 ，而 的绝对值是无关紧要的，我们可以将反向边流量的减少视为反向边剩余容量 的增加——这也与退流的意义相吻合——反向边剩余容量的增加意味着我们接下来可能通过走反向边来和原先正向的增广抵消，代表一种「反悔」的操作。

以下案例有可能帮助你理解这一过程。假设 是一个单位容量的网络，我们考虑以下过程：

• 上有多条增广路，其中，我们选择进行一次先后经过 的增广（如左图所示），流量增加 。
• 我们注意到，如果进行中图上的增广，这个局部的最大流量不是 而是 。但由于指向 的边和从 出发的边在第一次增广中耗尽了容量，此时我们无法进行中图上的增广。这意味着我们当前的流是不够优的，但局部可能已经没有其他（只经过原图中的边而不经过反向边的）增广路了。
• 现在引入退流操作。第一次增广后，退流意味着 增加了 剩余容量，即相当于新增 这条边，因此我们可以再进行一次先后经过 的增广（如右图橙色路径所示）。无向边 上的流量在两次增广中抵消，我们惊奇地发现两次增广叠加得到的结果实际上和中图是等价的。

以上案例告诉我们，退流操作带来的「抵消」效果使得我们无需担心我们按照「错误」的顺序选择了增广路。

容易发现，只要 上存在增广路，那么对其增广就可以令总流量增加；否则说明总流量已经达到最大可能值，求解过程完成。这就是 Ford–Fulkerson 增广的过程。

最大流最小割定理

我们大致了解了 Ford–Fulkerson 增广的思想，可是如何证明这一方法的正确性呢？为什么增广结束后的流 是一个最大流？

实际上，Ford–Fulkerson 增广的正确性和最大流最小割定理（The Maxflow-Mincut Theorem）等价。这一定理指出，对于任意网络 ，其上的最大流 和最小割 总是满足 。

为了证明最大流最小割定理，我们先从一个引理出发：对于网络 ，任取一个流 和一个割 ，总是有 ，其中等号成立当且仅当 的所有边均满流，且 的所有边均空流。

证明

为了取等，第一个不等号需要 的所有边均空流，第二个不等号需要 的所有边均满流。原引理得证。

那么，对于任意网络，以上取等条件是否总是能被满足呢？如果答案是肯定的，则最大流最小割定理得证。以下我们尝试证明。

容易看出，Kőnig 定理是最大流最小割定理的特殊情形。实际上，它们都和线性规划中的对偶有关。

时间复杂度分析

在整数流量的网络 上，平凡地，我们假设每次增广的流量都是整数，则 Ford–Fulkerson 增广的时间复杂度的一个上界是 ，其中 是 上的最大流。这是因为单轮增广的时间复杂度是 ，而增广会导致总流量增加，故增广轮数不可能超过 。

对于 Ford–Fulkerson 增广的不同实现，时间复杂度也各不相同。其中较主流的实现有 Edmonds–Karp, Dinic, SAP, ISAP 等算法，我们将在下文中分别介绍。

Edmonds–Karp 算法

算法思想

如何在 中寻找增广路呢？当我们考虑 Ford–Fulkerson 增广的具体实现时，最自然的方案就是使用 BFS。此时，Ford–Fulkerson 增广表现为 Edmonds–Karp 算法。其具体流程如下：

• 如果在 上我们可以从 出发 BFS 到 ，则我们找到了新的增广路。

• 对于增广路 ，我们计算出 经过的边的剩余容量的最小值 。我们给 上的每条边都加上 流量，并给它们的反向边都退掉 流量，令最大流增加了 。

• 因为我们修改了流量，所以我们得到新的 ，我们在新的 上重复上述过程，直至增广路不存在，则流量不再增加。

以上算法即 Edmonds–Karp 算法。

时间复杂度分析

接下来让我们尝试分析 Edmonds–Karp 算法的时间复杂度。

显然，单轮 BFS 增广的时间复杂度是 。

增广总轮数的上界是 。这一论断在网络资料中常被伪证（或被含糊其辞略过）。以下我们尝试给出一个较正式的证明¹。

将单轮 BFS 增广的复杂度与增广轮数的上界相乘，我们得到 Edmonds–Karp 算法的时间复杂度是 。

代码实现

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

#define maxn 250
#define INF 0x3f3f3f3f

struct Edge {
  int from, to, cap, flow;

  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct EK {
  int n, m;             // n：点数，m：边数
  vector<Edge> edges;   // edges：所有边的集合
  vector<int> G[maxn];  // G：点 x -> x 的所有边在 edges 中的下标
  int a[maxn], p[maxn];  // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
                         // p：点 x -> BFS 过程中最近接近点 x 的边

  void init(int n) {
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  int Maxflow(int s, int t) {
    int flow = 0;
    for (;;) {
      memset(a, 0, sizeof(a));
      queue<int> Q;
      Q.push(s);
      a[s] = INF;
      while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for (int i = 0; i < G[x].size(); i++) {  // 遍历以 x 作为起点的边
          Edge& e = edges[G[x][i]];
          if (!a[e.to] && e.cap > e.flow) {
            p[e.to] = G[x][i];  // G[x][i] 是最近接近点 e.to 的边
            a[e.to] =
                min(a[x], e.cap - e.flow);  // 最近接近点 e.to 的边赋给它的流
            Q.push(e.to);
          }
        }
        if (a[t]) break;  // 如果汇点接受到了流，就退出 BFS
      }
      if (!a[t])
        break;  // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
      for (int u = t; u != s;
           u = edges[p[u]].from) {  // 通过 u 追寻 BFS 过程中 s -> t 的路径
        edges[p[u]].flow += a[t];      // 增加路径上边的 flow 值
        edges[p[u] ^ 1].flow -= a[t];  // 减小反向路径的 flow 值
      }
      flow += a[t];
    }
    return flow;
  }
};

Dinic 算法

算法思想

考虑在增广前先对 做 BFS 分层，即根据结点 到源点 的距离 把结点分成若干层。令经过 的流量只能流向下一层的结点 ，即删除 向层数标号相等或更小的结点的出边，我们称 剩下的部分为层次图（Level Graph）。形式化地，我们称 是 的层次图，其中 。

如果我们在层次图 上找到一个最大的增广流 ，使得仅在 上是不可能找出更大的增广流的，则我们称 是 的阻塞流（Blocking Flow）。

定义层次图和阻塞流后，Dinic 算法的流程如下。

1. 在 上 BFS 出层次图 。
2. 在 上 DFS 出阻塞流 。
3. 将 并到原先的流 中，即 。
4. 重复以上过程直到不存在从 到 的路径。

此时的 即为最大流。

在分析这一算法的复杂度之前，我们需要特别说明「在 上 DFS 出阻塞流 」的过程。尽管 BFS 层次图对于本页面的读者应当是 trivial 的，但 DFS 阻塞流的过程则稍需技巧——我们需要引入当前弧优化。

注意到在 上 DFS 的过程中，如果结点 同时具有大量入边和出边，并且 每次接受来自入边的流量时都遍历出边表来决定将流量传递给哪条出边，则 这个局部的时间复杂度最坏可达 。为避免这一缺陷，如果某一时刻我们已经知道边 已经增广到极限（边 已无剩余容量或 的后侧已增广至阻塞），则 的流量没有必要再尝试流向出边 。据此，对于每个结点 ，我们维护 的出边表中第一条还有必要尝试的出边。习惯上，我们称维护的这个指针为当前弧，称这个做法为当前弧优化。

时间复杂度分析

应用当前弧优化后，对 Dinic 算法的时间复杂度分析如下。

首先，我们尝试证明单轮增广中 DFS 求阻塞流的时间复杂度是 。

注意到层次图的层数显然不可能超过 ，如果我们可以证明层次图的层数在增广过程中严格单增，则 Dinic 算法的增广轮数是 的。接下来我们尝试证明这一结论²。

将单轮增广的时间复杂度 与增广轮数 相乘，Dinic 算法的时间复杂度是 。

如果需要令 Dinic 算法的实际运行时间接近其理论上界，我们需要构造有特殊性质的网络作为输入。由于在算法竞赛实践中，对于网络流知识相关的考察常侧重于将原问题建模为网络流问题的技巧。此时，我们的建模通常不包含令 Dinic 算法执行缓慢的特殊性质；恰恰相反，Dinic 算法在大部分图上效率非常优秀。因此，网络流问题的数据范围通常较大，「将 的值代入 以估计运行时间」这一方式并不适用。实际上，进行准确的估计需要选手对 Dinic 算法的实际效率有一定的经验，读者可以多加练习。

特殊情形下的时间复杂度分析

在一些性质良好的图上，Dinic 算法有更好的时间复杂度。

对于网络 ，如果其所有边容量均为 ，即 对于 恒成立，则我们称 是单位容量（Unit Capacity）的。

在单位容量的网络中，Dinic 算法的单轮增广的时间复杂度为 。

在单位容量的网络中，Dinic 算法的增广轮数是 的。

在单位容量的网络中，Dinic 算法的增广轮数是 的。

在单位容量的网络中，如果除源汇点外每个结点 都满足 或 ，则 Dinic 算法的增广轮数是 的。其中， 和 分别代表结点 的入度和出度。

综上，我们得出一些推论。

• 在单位容量的网络上，Dinic 算法的总时间复杂度是 。
• 在单位容量的网络上，如果除源汇点外每个结点 都满足 或 ，Dinic 算法的总时间复杂度是 。对于二分图最大匹配问题，我们常使用 Hopcroft–Karp 算法解决，而这一算法实际上是 Dinic 算法在满足上述度数限制的单位容量网络上的特例。

代码实现

 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

struct MF {
  struct edge {
    int v, nxt, cap, flow;
  } e[N];

  int fir[N], cnt = 0;

  int n, S, T;
  ll maxflow = 0;
  int dep[N], cur[N];

  void init() {
    memset(fir, -1, sizeof fir);
    cnt = 0;
  }

  void addedge(int u, int v, int w) {
    e[cnt] = {v, fir[u], w, 0};
    fir[u] = cnt++;
    e[cnt] = {u, fir[v], 0, 0};
    fir[v] = cnt++;
  }

  bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof(int) * (n + 1));

    dep[S] = 1;
    q.push(S);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int i = fir[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if ((!dep[v]) && (e[i].cap > e[i].flow)) {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return dep[T];
  }

  int dfs(int u, int flow) {
    if ((u == T) || (!flow)) return flow;

    int ret = 0;
    for (int& i = cur[u]; ~i; i = e[i].nxt) {
      int v = e[i].v, d;
      if ((dep[v] == dep[u] + 1) &&
          (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {
        ret += d;
        e[i].flow += d;
        e[i ^ 1].flow -= d;
        if (ret == flow) return ret;
      }
    }
    return ret;
  }

  void dinic() {
    while (bfs()) {
      memcpy(cur, fir, sizeof(int) * (n + 1));
      maxflow += dfs(S, INF);
    }
  }
} mf;