P3386 【模板】二分图最大匹配 题解

1. 引入：

First . 二分图：

二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。

换言之，存在一种方案，将节点划分成满足以上性质的两个集合。

second . 二分图匹配：

在图论中，假设图 $G=(V,E)$。

其中 $V$ 是点集，$E$ 是边集。

一组两两没有公共点的边集 $M(M \in E)$ 称为这张图的匹配。

定义匹配的大小为其中边的数量 $|M|$，其中边数最大的 $M$ 为 最大匹配。

好多条无公共端点的边的集合叫这张二分图的一个匹配。（这里因为是二分图，所以边已经是连接两组点集 $U$，$V$ 的了，不需要加以限制）

匹配的大小为边的数量。

third . 二分图最大匹配：

假设图有 $n$ 个顶点，$m$ 条边。

给定一个二分图 G，要求选出一些边，使得这些边没有公共顶点，且边的数量最大。

2. 思路：

准备

算法过程：

先将 $0$ 号点连接到可以连接的第一个点即 $4$ 号。

然后将 $1$ 号点连接到可以连接的第一个点即 $5$ 号。

接着连接 $2$ 号点，但此时我们发现 $2$ 号点应该连接的 $4$ 号被 $0$ 号占用了。 这时，我们将 $0$ 号点与 $4$ 号点间的连接断开。

这时发现 $0$ 号点和 $1$ 号点同时连接到了 $5$ 号点，与二分图最大匹配的定义不符，所以再为 $1$ 号点重新连接到 $6$ 号点。

于是就可以把 $2$ 号点与 $4$ 号点连接起来了。

再往后的 $3$ 号点应连接到的 $6$ 号点被占用，无法连接，算法结束。 最大匹配值即为已连接上的边的数量。

3. 证明：

交错路：始于非匹配点由匹配边于非匹配边交错而成的路径。

增广路：始于非匹配点且终于非匹配点（除了起始的点）的交错路。增广路中边的数量是奇数。

推论 1. 增广路中匹配边数量比非匹配边数量少一。

1. 在匈牙利算法中，我们通过寻找每个未匹配点的增广路来增加匹配数量。
2. 匈牙利算法结束时意味着没有增广路了。

匈牙利算法得到的匹配为这个二分图的最大匹配。

二分图的最大匹配中不存在增广路。

二分图的最大匹配中有增广路。

假设二分图最大匹配中有增广路：

则根据推论 1，我们将图中匹配边与非匹配边反转后，得到一个新的匹配。

原非匹配边反转成了匹配边，此时相当于匹配边 $+1$。

所以，此时原图中存在更大的匹配。

故原命题不成立。

证毕。

4.Code：

#include<iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1005;

int n, m, t;
int mch[maxn], vistime[maxn];

vector<int> e[maxn];

bool dfs(const int u, const int tag);

int main() {
  scanf("%d %d %d", &n, &m, &t);
  for (int u, v; t; --t) {
    scanf("%d %d", &u, &v);
    e[u].push_back(v);
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) if (dfs(i, i)) {
    ++ans;
  }
  printf("%d\n", ans);
}

bool dfs(const int u, const int tag) {
  if (vistime[u] == tag) return false;
  vistime[u] = tag;
  for (auto v:e[u]) if ((mch[v] == 0) || dfs(mch[v], tag)) {
    mch[v] = u;
    return true;
  }
  return false;
}

通关记录：

5. 参考资料：

1. OIWiKi。
2. Loi23 级学长课件。