二分图最大匹配

引入

本文讨论二分图 $G = (X, Y, E)$ 的最大匹配问题。

生活中一个典型的二分图匹配的例子是男女配对。设有若干男生（ $X$ ）和女生（ $Y$ ），每个人只能配对一次，且允许配对的组合已由某个列表（ $E$ ）限定。此时，二分图最大匹配算法的任务就是在这些限制下，找到最多的配对对数，使尽可能多的人成功配对。

提示

本文假设已知二分图顶点集 $V$ 的一种划分（染色）方式： $V = X \cup Y$ 。如果事先不清楚二分图的顶点集 $V$ 的划分方法，可以通过二分图的染色算法在 $O (| V | + | E |)$ 时间内求出这样一个划分。

Kuhn 算法

Kuhn 算法是 Berge 引理的直接应用。它也是匈牙利算法的一部分。

过程

为了求出最大匹配，算法依次枚举所有顶点，求出从它出发的一条增广路，并进行增广。因为增广路的长度总是奇数，所以在二分图中，它的端点必然分别位于左右两个部分。这说明，只需要考虑从左部出发的增广路即可。

为了寻找增广路，可以依据当前的匹配 $M$ 给二分图定向。从左部的未匹配点出发的增广路（或者任何一条交错路）中，只能沿着非匹配边从左部点到达右部点，再沿着匹配边从右部点到达左部点。因此，可以规定所有非匹配边都指向右部点，而所有匹配边都指向左部点。寻找增广路的问题就转换为从某个未匹配的左部点出发，在有向图中寻找一条简单路径通向某个未匹配点。这一问题很容易通过 DFS 或 BFS 在 $O (| E |)$ 时间内解决。

（图中，深色点为匹配点，浅色点为未匹配点，红边为匹配边，黑边为非匹配边，箭头表示当前匹配对应的定向。由图可知，路径 $1 \to 8 \to 3 \to 11 \to 6 \to 12$ 是相对于当前匹配的一条增广路。）

算法开始时，所有边都指向右部点。每次寻找到增广路后，都需要沿着增广路将经过的所有边都反向，以表示它们的匹配状态已经反转。算法结束时，所有指向左部点的边就是匹配边。

因为至多只需要枚举 $O (| V |)$ 个左部点各一次，所以，算法总的时间复杂度为 $O (| V | | E |)$ 。

优化

有一些简单的技巧，可以优化 Kuhn 算法的常数：

Kuhn 算法基于 Berge 引理，而后者并不要求事先给出二分图的左右部分。因此，即使在左右两部分未明确划分的情况下，Kuhn 算法也能正确运行，只要图本身是二分图。但是，先将二分图染色，确定好它的左部和右部，往往效率更高。
因为上文描述的 Kuhn 算法的时间复杂度实际上是 $O (| X | | E |)$ 的，所以，可以选取二分图的两个部分中较小的那个作为左部 $X$ 。
在寻找增广路时，用于避免重复查找的标记无需每次 DFS 都清空。可以在清空标记前，尝试为所有未匹配的左部点都寻找增广路。在一轮这样的查找中，所有边至多访问一次，复杂度仍然是 $O (| E |)$ 的；但是，在一轮查找中，可能找到多条增广路，因此总的轮数 $k$ 不会超过 $| M | + 1$ ，其中， $M$ 为最大匹配。相应地，算法整体复杂度降低到了 $O (k | E |)$ 。
寻找增广路时，优先考虑未匹配的右部点，因为这意味着更短的增广路。
因为 Berge 引理并不要求初始匹配为空，所以，Kuhn 算法开始时，可以随机地选取一些互不相交的边作为初始匹配，以减少后续搜索的次数。如果已经应用优化 3，本优化可以忽略。

虽然最差复杂度仍然是 $O (| V | | E |)$ ，但是，充分优化的 Kuhn 算法效率并不差。但是为了避免个别数据将它卡到最差复杂度，在匹配前需要首先随机打乱边或顶点的顺序。

参考实现

实现时，不需要真正维护定向，只需要为每个顶点都维护与它相匹配的顶点即可。

模板题 Library Checker - Matching on Bipartite Graph

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>
#include <tuple>
#include <vector>

std::mt19937_64 rng(
    static_cast<std::mt19937_64::result_type>(std::time(nullptr)));

struct BipartiteGraph {
  int n1, n2;                       // number of vertices in X and Y, resp.
  std::vector<std::vector<int>> g;  // edges from X to Y
  std::vector<int> ma, mb;  // matches from X to Y and from Y to X, resp.
  std::vector<bool> vis;    // visiting marks for DFS.

  BipartiteGraph(int n1, int n2)
      : n1(n1), n2(n2), g(n1), ma(n1, -1), mb(n2, -1) {}

  // Add an edge from u in X to v in Y.
  void add_edge(int u, int v) { g[u].emplace_back(v); }

  // Find an augmenting path starting at u.
  bool dfs(int u) {
    vis[u] = true;
    // Heuristic: find unsaturated vertices whenever possible.
    for (int v : g[u]) {
      if (mb[v] == -1) {
        ma[u] = v;
        mb[v] = u;
        return true;
      }
    }
    for (int v : g[u]) {
      if (!vis[mb[v]] && dfs(mb[v])) {
        ma[u] = v;
        mb[v] = u;
        return true;
      }
    }
    return false;
  }

  // Kuhn's maximum matching algorithm.
  std::vector<std::pair<int, int>> kuhn_maximum_matching() {
    // Randomly shuffle the edges.
    for (int u = 0; u < n1; ++u) {
      std::shuffle(g[u].begin(), g[u].end(), rng);
    }
    // Find a maximal set of vertex-disjoint augmenting paths in each round.
    while (true) {
      bool succ = false;
      vis.assign(n1, false);
      for (int u = 0; u < n1; ++u) {
        succ |= ma[u] == -1 && dfs(u);
      }
      if (!succ) break;
    }
    // Collect the matched pairs.
    std::vector<std::pair<int, int>> matches;
    matches.reserve(n1);
    for (int u = 0; u < n1; ++u) {
      if (ma[u] != -1) {
        matches.emplace_back(u, ma[u]);
      }
    }
    return matches;
  }
};

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  int n1, n2, m;
  std::cin >> n1 >> n2 >> m;
  BipartiteGraph gr(n1, n2);
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    gr.add_edge(u, v);
  }
  auto res = gr.kuhn_maximum_matching();
  std::cout << res.size() << '\n';
  for (int i = 0; i < res.size(); ++i) {
    std::cout << res[i].first << ' ' << res[i].second << '\n';
  }
  return 0;
}

Hopcroft–Karp 算法

Hopcroft–Karp 算法进一步优化了 Kuhn 算法查找增广路的过程，将总的轮数降低到了 $O (| V |^{1 / 2})$ ，从而获得了 $O (| V |^{1 / 2} | E |)$ 的时间复杂度。这一算法实际上是 Dinic 算法的一种特殊情形。

过程

算法依然是在寻找增广路，但是为了在更少的轮次内完成匹配，算法在每一轮中都采取了如下策略：

将匹配边定向为指向左部点，非匹配边定向为指向右部点。
从所有未匹配的左部点出发，在有向图上进行 BFS，记录每个访问到的顶点所在的层数 $d (v)$ ，直到某一层出现未匹配的右部点为止。若 BFS 结束仍未找到未匹配的右部点，说明当前匹配已是最大匹配。
依次从每个未匹配的左部点出发进行 DFS，寻找增广路并进行增广。DFS 时沿着满足层数连续且严格递增（即 $d (v^{'}) = d (v) + 1$ ）的边向前扩展，且只访问尚未在本轮 DFS 中访问过的顶点。特别地，DFS 中不会访问到前一步 BFS 中尚未访问到的顶点。

用网络流的术语说，步骤 2 是构造了一个层次图，而步骤 3 则是找到了层次图上的阻塞流。所谓层次图，是指它的每条边都必然从这一层指向下一层；而所谓阻塞流，在当前语境下，就是指一组极大的、两两之间没有公共顶点的增广路。步骤 3 得到的这一组增广路必然是极大的：假设不然，存在一条新的增广路，那么在当初枚举到它的起点时，就应当已经找到这样一条路。

比起前文的 Kuhn 算法，Hopcroft–Karp 算法最关键的改变就是在求阻塞流之前，添加了求层次图这一步骤。基于层次图进行 DFS，相当于限制了算法总是沿着最短路径到达各个顶点。这样做的好处是，在算法的不同轮次间，算法找到的增广路的长度是严格递增的。而且，可以证明的是，直到求出最大匹配为止，增广路的长度至多增加 $3 | M |^{1 / 2}$ 次，其中， $| M |$ 为最大匹配的大小。所以，这就将总的增广的轮次控制在 $O (| M |^{1 / 2})$ ，进而得到 $O (| M |^{1 / 2} | E |)$ 的时间复杂度。由于 $2 | M | \leq | V |$ ，所以，时间复杂度也可以写成更宽松的上界 $O (| V |^{1 / 2} | E |)$ 。

证明

首先说明，在算法的不同轮次之间，算法找到的增广路的长度是严格递增的。

假设当前轮次的 BFS 中，顶点向前延伸了 $ℓ$ 层，那么，因为 BFS 中找到的未匹配的右部点都位于同一层，所以本轮 DFS 能够找到的所有增广路的长度就都是 $ℓ$ 。需要证明的是，沿着本轮找到的这组增广路 ${P_{i}}$ 增广结束后，重新定向得到的有向图中，将不再存在长度不超过 $ℓ$ 的增广路。

实际上，如果 $P$ 是相对于 $M$ 的最短的增广路，而 $P^{'}$ 是相对于 $M \oplus P$ 的增广路，都有 $| P^{'} | \geq | P | + 2 | P \cap P^{'} |$ 成立。这是因为 $N = (M \oplus P) \oplus P^{'}$ 相对于 $M$ 增广了两次，故而类似 Berge 引理的证明，可以说明对称差 $M \oplus N = P \oplus P^{'}$ 中至少包含两条相对于 $M$ 的不交的增广路 $P_{1}$ 和 $P_{2}$ 。由于 $P$ 的最短性，有

2 | P | \leq | P_{1} | + | P_{2} | \leq | P \oplus P^{'} | = | P | + | P^{'} | - 2 | P \cap P^{'} | .

这就说明 $| P^{'} | \geq | P | + 2 | P \cap P^{'} |$ 。因此，如果添加完增广路 ${P_{i}}$ 之后，新的增广路 $P^{'}$ 仍然和它们一样长，就必然与它两两不交，这与 ${P_{i}}$ 的极大性相矛盾。这一矛盾说明，增广完阻塞流后，新的增广路一定严格更长。

最后，需要说明，增广路的长度至多增加 $3 | M |^{1 / 2}$ 次。

记 $p = ⌊ | M |^{1 / 2} ⌋$ 。在前 $p$ 个轮次结束后，剩下的增广路的长度至少是 $| M |^{1 / 2}$ 。设当前匹配为 $M_{p}$ ，那么，与前文情形类似，可以说明图 $(V, M \oplus M_{p})$ 中有 $| M | - | M_{p} |$ 条两两之间没有公共顶点的相对于 $M_{p}$ 的增广路。每条增广路至少用到 $| M |^{1 / 2} / 2$ 条 $M$ 中的匹配边，因此，这些增广路的总数不会超过 $2 | M |^{1 / 2}$ ，也就是说， $| M | - | M_{p} | \leq 2 | M |^{1 / 2}$ 。这说明从 $M_{p}$ 开始，至多只能再增广 $2 | M |^{1 / 2}$ 次，这同样意味着算法至多再进行 $2 | M |^{1 / 2}$ 轮增广。所以，增广路的长度总共至多增加 $3 | M |^{1 / 2}$ 次。

这仅仅是对 Hopcroft–Karp 算法的最差复杂度的估计。实际上，在随机图中，Hopcroft–Karp 算法的时间复杂度有很大概率是 $O (| E | \log | V |)$ 的¹。

优化

在建立层次图时，和一般的 Dinic 算法一样，Hopcroft–Karp 算法在到达未匹配的右部点时就终止。但是，仅仅就二分图匹配问题来说，这样做是没有必要的。而且，因为 BFS 过早终止，限制了后续 DFS 的范围，会导致每轮找到的增广路数目有限，从而拖慢整体匹配效率。在有些图上，它的效率甚至不如经过优化的 Kuhn 算法。所以，一个简单的改进是，不提前终止 BFS，而是为所有可以到达的顶点建立层次图。

正确性证明

在优化后的算法中，阻塞流中增广路的长度将不再相同，因此，前文中关于复杂度的证明也不再成立。但是，可以说明的是，通过为算法的每个轮次建立辅助图，同样可以建立最短增广路长度严格递增的结论，进而保证最差复杂度依然是正确的。

设二分图为 $G = (X, Y, E)$ ，当前的匹配为 $M$ 。设通过 BFS 可以访问到的未匹配的右部点的集合为 $W \subseteq Y$ ，且到达 $y \in W$ 的最短的增广路的长度为 $d (y)$ 。记 $d_{max} = max_{y \in W} d (y)$ ，那么，对于每个 $y \in W$ ，都可以新建一条从 $y$ 开始且长度为 $d_{max} - d (y)$ 的链，并将新建的顶点依次标记为左部点和右部点，将新建的边依次标记为匹配边和非匹配边。设这样得到的图为 $G^{'} = (X^{'}, Y^{'}, E^{'})$ ，匹配为 $M^{'}$ ，最短增广路的长度为 $d_{max}$ 。那么，图 $G$ 中沿着层次图能够找到的相对于 $M$ 的增广路——也就是那些到达相应顶点的最短的增广路——与图 $G^{'}$ 中相对于 $M^{'}$ 的全局最短的增广路之间存在双射。因此，在图 $G$ 的层次图中找到阻塞流并进行增广，就相当于在图 $G^{'}$ 的层次图中找到阻塞流并进行增广。按照前文的证明，增广后，图 $G^{'}$ 中将不再存在长度为 $d_{max}$ 的增广路。所以，图 $G$ 中也不再存在长度为 $d_{min} = min_{y \in W} d (y)$ 的增广路：因为这样的增广路通过新延长的交错路，必然对应着一条图 $G^{'}$ 中长度为 $d_{max}$ 的增广路。这样就再次得到了算法的不同轮次间，最短增广路的长度严格递增的结论。因此，整体复杂度也仍然是 $O (| M |^{1 / 2} | E |)$ 的。

参考实现

模板题 Library Checker - Matching on Bipartite Graph

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

struct BipartiteGraph {
  int n1, n2;                       // number of vertices in X and Y, resp.
  std::vector<std::vector<int>> g;  // edges from X to Y
  std::vector<int> ma, mb;  // matches from X to Y and from Y to X, resp.
  std::vector<int> dist;    // distance from unsaturated vertices in X.

  BipartiteGraph(int n1, int n2)
      : n1(n1), n2(n2), g(n1), ma(n1, -1), mb(n2, -1) {}

  // Add an edge from u in X to v in Y.
  void add_edge(int u, int v) { g[u].emplace_back(v); }

  // Build the level graph.
  bool bfs() {
    dist.assign(n1, -1);
    std::queue<int> q;
    for (int u = 0; u < n1; ++u) {
      if (ma[u] == -1) {
        dist[u] = 0;
        q.emplace(u);
      }
    }
    // Build the level graph for all reachable vertices.
    bool succ = false;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : g[u]) {
        if (mb[v] == -1) {
          succ = true;
        } else if (dist[mb[v]] == -1) {
          dist[mb[v]] = dist[u] + 1;
          q.emplace(mb[v]);
        }
      }
    }
    return succ;
  }

  // Find an augmenting path starting at u.
  bool dfs(int u) {
    for (int v : g[u]) {
      if (mb[v] == -1 || (dist[mb[v]] == dist[u] + 1 && dfs(mb[v]))) {
        ma[u] = v;
        mb[v] = u;
        return true;
      }
    }
    dist[u] = -1;  // Mark this point as inreachable after one visit.
    return false;
  }

  // Hopcroft-Karp maximum matching algorithm.
  std::vector<std::pair<int, int>> hopcroft_karp_maximum_matching() {
    // Build the level graph and then find a blocking flow.
    while (bfs()) {
      for (int u = 0; u < n1; ++u) {
        if (ma[u] == -1) {
          dfs(u);
        }
      }
    }
    // Collect the matched pairs.
    std::vector<std::pair<int, int>> matches;
    matches.reserve(n1);
    for (int u = 0; u < n1; ++u) {
      if (ma[u] != -1) {
        matches.emplace_back(u, ma[u]);
      }
    }
    return matches;
  }
};

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  int n1, n2, m;
  std::cin >> n1 >> n2 >> m;
  BipartiteGraph gr(n1, n2);
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    gr.add_edge(u, v);
  }
  auto res = gr.hopcroft_karp_maximum_matching();
  std::cout << res.size() << '\n';
  for (int i = 0; i < res.size(); ++i) {
    std::cout << res[i].first << ' ' << res[i].second << '\n';
  }
  return 0;
}

归约为最大流问题

二分图最大匹配问题可以归约为最大流问题。

如图所示，添加两个顶点分别作为源点和汇点。从源点出发，向每个左部点连接一条边；从每个右部点出发，向汇点连接一条边；并为二分图中的每条无向边，都连接一条从左部点指向右部点的边。所有边的容量都是 $1$ 。这样得到的有向图中的每个网络流，都和二分图中的一组匹配一一对应，且网络流的容量就是相应的匹配的大小。因此，求解二分图最大匹配，就相当于求解相应的有向图中的最大流。

任何可以解决最大流问题的算法都可以用于解决二分图最大匹配问题。容易发现，Kuhn 算法和 Hopcroft–Karp 算法都是最大流问题中相应算法的特例。同样地，预流推进算法等同样可以用于解决二分图最大匹配问题。但是，应当注意的是，任何最大流算法，在应用于二分图最大匹配问题时，都需要有针对性地进行相应的优化，以避免过大的常数。

线性规划形式

和其他最大流问题一样，二分图 $G = (V, E)$ 的最大匹配问题可以写作线性规划问题。如果用 $x_{e} \in {0, 1}$ 表示边 $e$ 是否属于匹配，那么，可以得到如下的线性规划问题：

\begin{aligned} max_{{x_{e}}} & \sum_{e \in E} x_{e} \\ subject to & \sum_{e \sim v} x_{e} \leq 1, \forall v \in V, \\ x_{e} \geq 0, \forall e \in E . \end{aligned}

其中， $e \sim v$ 表示关联关系，即顶点 $v$ 是边 $e$ 的端点之一。除了非负限制之外，问题的约束还要求每个顶点 $v \in V$ 处至多与一条边关联，这正是匹配的定义。因此，所有的匹配都对应于该线性规划可行域中的某些整点。

反过来却不然。在可行解中， $x_{e}$ 可能是小数，这并不代表任何实际的匹配。尽管如此，对于二分图 $G$ ，上述线性规划的所有极点解都是整点。这意味着，目标函数的最优值总能在整点处取得，而无需考虑非整数的情形。这一性质对一般图并不成立，因此，上述线性规划在一般图中并不等价于最大匹配问题。

这一线性规划问题的对偶问题可以写作如下形式：

\begin{aligned} min_{{y_{v}}} & \sum_{v \in V} y_{v} \\ subject to & y_{u} + y_{v} \geq 1, \forall (u, v) \in E, \\ y_{v} \geq 0, \forall v \in V . \end{aligned}

马上就会看到，这正是二分图的最小点覆盖问题。

例题

应用二分图匹配的难点在于建图，本节通过一些例题展示建图的技巧。

Luogu P1129 矩阵游戏

有一个 01 方阵，每一次可以交换两行或两列，问是否可以交换使得主对角线（左上到右下）全都是 1。

解法

注意到，当存在 $n$ 个 $1$ ，使得这些 $1$ 不在同一行、同一列，那么必然有解，否则必然无解。问题转化成了能否找到这 $n$ 个 $1$ 。

考虑对于一个 $1$ 而言，最终的方案中选了这个 $1$ 代表这个 $1$ 的行、列被占用。于是可以建出一个 $n$ 个左部点、 $n$ 个右部点的二分图，其中对于某个为 $1$ 的元素，我们建一条连接它的行的左部点和它的列的右部点。于是就可以二分图匹配了。

代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int ct, n, t[100010], x, r[100010], ans, vis[100010], dis[100010];
vector<int> to[100010];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + n + 1, 0);
  fill(dis + 1, dis + n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  for (cin >> ct; ct--;) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        cin >> x;
        if (x) {
          to[i].push_back(j);
        }
      }
    }
    for (; BFS();) {
      for (int i = 1; i <= n; i++) {
        if (!t[i] && DFS(i)) {
          ans++;
        }
      }
    }
    cout << (ans == n ? "Yes" : "No") << '\n';
    for (int i = 1; i <= n; i++) {
      t[i] = r[i] = 0;
      to[i].clear();
    }
    ans = 0;
  }
  return 0;
}

Gym 104427B Lawyers

有 $n$ 个律师，都被指控有欺诈罪。于是，他们需要互相辩护，确保每一名律师都被释放。这 $n$ 个律师有 $m$ 对信任关系，一个信任关系 $(a, b)$ 表示 $a$ 可以为 $b$ 辩护。任何一个受到辩护的律师都会被无罪释放，除了一个例外：如果 $a$ 和 $b$ 互相辩护，他们都会被判有罪。

求是否可以使得每一名律师都被释放。

解法

对于每一个 无序对 $(a, b)$ ，当 $a$ 可以辩护 $b$ ，连这个无序对向 $a$ 的边，反之亦然。

只保存有边相连的 $(a, b)$ ，问题被转化成了一个 $m$ 个左部点、 $n$ 个右部点的二分图最大匹配。

代码

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int n, k, u, v, t[200020], r[200020], ans, vis[200020], dis[200020], c;
map<pair<int, int>, int> mp;
vector<int> to[200020];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + n + 1, 0);
  fill(dis + 1, dis + n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

void mxf() {
  for (; BFS();) {
    for (int i = 1; i <= n; i++) {
      if (!t[i] && DFS(i)) {
        ans++;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    cin >> u >> v;
    if (mp.find({u, v}) == mp.end()) {
      mp[{u, v}] = mp[{v, u}] = ++c;
    }
    to[v].push_back({mp[{u, v}]});
  }
  mxf();
  cout << (ans == n ? "YES" : "NO") << '\n';
  ans = 0;
  return 0;
}

Codeforces 1404E Bricks

用一些 $1 \times x$ 的砖精确覆盖一个 $n \times m$ 的网格，砖可以旋转，其中有一些格子不能覆盖。

解法

考虑最终的方案是如何构成的：

先在所有能覆盖的网格上全部铺上 $1 \times 1$ 的砖。对于一个 $1 \times x$ 的砖，可以由同一行的 $x$ 个连续的 $1 \times 1$ 砖依次「行合并」形成。同理，对于一个 $x \times 1$ 的砖。可以由同一列的 $x$ 个连续的 $1 \times 1$ 砖依次「列合并」形成。

显然，一次行合并和一次列合并不能干涉到同一个砖，而且合并的次数越多，砖块数量越少。于是，可以以行合并作为左部点，列合并作为右部点，以前面的冲突作为边，建出一个二分图。随即原问题变成了一个二分图最大独立集问题。

代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n, m, belr[220][220], beld[220][220], dcnt, rcnt, vis[100010], dis[100010],
    t[100010], r[100010], cnt;
char c[220][220];
vector<int> to[100010];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + rcnt + 1, 0);
  fill(dis + 1, dis + rcnt + 1, 0);
  for (int i = 1; i <= rcnt; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

int solve() {
  int rt = 0;
  for (; BFS();) {
    for (int i = 1; i <= rcnt; i++) {
      if (!t[i] && DFS(i)) {
        rt++;
      }
    }
  }
  return rt;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> c[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (c[i][j] == '#') {
        cnt++;
        if (c[i + 1][j] == '#') {
          beld[i][j] = ++dcnt;
        }
        if (c[i][j + 1] == '#') {
          belr[i][j] = ++rcnt;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (c[i][j] == '#') {
        if (c[i - 1][j] == '#' && c[i][j - 1] == '#') {
          to[belr[i][j - 1]].push_back(beld[i - 1][j]);
        }
        if (c[i + 1][j] == '#' && c[i][j + 1] == '#') {
          to[belr[i][j]].push_back(beld[i][j]);
        }
        if (c[i + 1][j] == '#' && c[i][j - 1] == '#') {
          to[belr[i][j - 1]].push_back(beld[i][j]);
        }
        if (c[i - 1][j] == '#' && c[i][j + 1] == '#') {
          to[belr[i][j]].push_back(beld[i - 1][j]);
        }
      }
    }
  }
  cout << cnt - rcnt - dcnt + solve() << '\n';
  return 0;
}

Codeforces 1139E - Maximize Mex

有 $m$ 个共有 $n$ 个元素的可重集，每一次从某一个可重集里面删除一个元素，然后查询「在每一个可重集里面选至多一个元素，可以达到的最大 $mex$ 」。

解法

先考虑如果没有删除元素时怎么做。

对于每一个多重集，开一个新点；对于每一个可能的答案，开一个新点。然后，对于某一个对应点 $l_{i}$ 的多重集的一个元素 $a$ ，连一条 $l_{i}$ 至 $r_{a}$ 的边。此时这个弱化版本变成了一个二分图最大匹配。

现在加回来删除元素的操作，发现根本搞不了：删了一条边可能引起匹配的巨变，复杂度无法接受。于是，不如反过来，我们每一次加一条边，然后顺过去重新增广。所以本题只能使用 Kuhn 算法。

代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct node {
  int u, v;
} arr[5050];

int n, m, t[5050], r[5050], d, ot[5050], kil[5050], vis[5050], ans, out[5050];
vector<int> to[5050];

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (r[i] == -1) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i].u;
    if (arr[i].u > m) {
      arr[i].u = m + 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    cin >> arr[i].v;
  }
  cin >> d;
  for (int i = 1; i <= d; i++) {
    cin >> ot[i];
    kil[ot[i]] = 1;
  }
  for (int i = 1; i <= n; i++) {
    if (!kil[i]) {
      to[arr[i].u].push_back(arr[i].v);
    }
  }
  fill(r + 1, r + m + 1, -1);
  for (; ans <= m;) {
    fill(vis, vis + m + 2, 0);
    if (DFS(ans)) {
      ans++;
    } else {
      break;
    }
  }
  out[d] = ans;
  for (int i = d; i > 1; i--) {
    to[arr[ot[i]].u].push_back(arr[ot[i]].v);
    for (; ans <= m;) {
      fill(vis, vis + m + 2, 0);
      if (DFS(ans)) {
        ans++;
      } else {
        break;
      }
    }
    out[i - 1] = ans;
  }
  for (int i = 1; i <= d; i++) {
    cout << out[i] << '\n';
  }
  return 0;
}

Luogu P3355 - 骑士共存问题

有一个 $n \times n$ 的国际象棋棋盘，其中一些位置不能放棋子，问最多可以放多少个马使得这些马不会互相攻击。

解法

可以发现，如果对整个棋盘染色使得所有黑格、白格均不相邻，那么马只能够攻击到与其异色的格子。

然后就可以直接二分图最大独立集了。

代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int kD[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
                      {2, 1},   {1, 2},   {-1, 2}, {-2, 1}};

int n, m, ib;
int vis[200020], dis[200020], t[200020], r[200020], ans, u, v, cnta,
    x[220][220], cl[220][220], idx, bel[220][220];
vector<int> to[200020];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return false;
  }
  vis[x] = true;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return true;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return true;
    }
  }
  return false;
}

int BFS() {
  fill(vis + 1, vis + cnta + 1, false);
  fill(dis + 1, dis + cnta + 1, 0);
  for (int i = 1; i <= cnta; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

void din() {
  for (; BFS();) {
    for (int i = 1; i <= cnta; i++) {
      if (!t[i] && DFS(i)) {
        ans++;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v;
    x[u][v] = true;
  }
  cl[1][1] = 1;
  if (!x[1][1]) {
    bel[1][1] = ++idx;
  }
  for (int i = 2; i <= n; i++) {
    cl[1][i] = cl[1][i - 1] ^ 1;
    if (!x[1][i] && cl[1][i]) {
      bel[1][i] = ++idx;
    } else {
      if (!x[1][i]) {
        bel[1][i] = ++ib;
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cl[i][j] = cl[i - 1][j] ^ 1;
      if (!x[i][j] && cl[i][j]) {
        bel[i][j] = ++idx;
      } else {
        if (!x[i][j]) {
          bel[i][j] = ++ib;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!x[i][j]) {
        cnta += cl[i][j];
        for (int k = 0; k < 8; k++) {
          if (i + kD[k][0] > 0 && j + kD[k][1] > 0 &&
              bel[i + kD[k][0]][j + kD[k][1]] &&
              !x[i + kD[k][0]][j + kD[k][1]]) {
            if (cl[i + kD[k][0]][j + kD[k][1]]) {
              to[bel[i + kD[k][0]][j + kD[k][1]]].push_back(bel[i][j]);
            } else {
              to[bel[i][j]].push_back(bel[i + kD[k][0]][j + kD[k][1]]);
            }
          }
        }
      }
    }
  }
  din();
  cout << n * n - m - ans << '\n';
  return 0;
}

习题

参考资料

Kuhn's Algorithm - Maximum Bipartite Matching
二分图最大匹配的 König 定理及其证明
Implementing Dinitz on bipartite graphs by adamant - Codeforces blogs
Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty. Graph theory with applications. Vol. 290. London: Macmillan, 1976.

Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao (2006), "Matching algorithms are fast in sparse random graphs", Theory of Computing Systems, 39 (1): 3–14. ↩

本页面最近更新：2025/6/26 13:11:55，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：5ab-juruo, Chrogeek, countercurrent-time, Enter-tainer, H-J-Granger, Henry-ZHR, hhc0001, ksyx, StudyingFather, thallium, william-song-shy, 310552025atNYCU, accelsao, billchenchina, c-forrest, CCXXXI, Early0v0, Great-designer, Haohu Shen, HeRaNO, iamtwz, NachtgeistW, ouuan, SukkaW, TianKong-y, Tiphereth-A, Xeonacid, XiaoQuQuSD
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

二分图最大匹配

引入

Kuhn 算法

过程

优化

参考实现

Hopcroft–Karp 算法

过程

优化

参考实现

归约为最大流问题

线性规划形式

相关问题

二分图最小点覆盖

二分图最大独立集

有向无环图最小路径覆盖

例题

习题

参考资料