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

· · 题解

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

1. 引入：

First . 二分图：

既然要学习二分图最大匹配，肯定先要了解啥是二分图。

OI wiki 上说：

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

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

就是把一个图上的点分成两组，每一条边都连接不同组的点。

在图中表示为每一条边都从 U 组的点连到 V 组的点，不会从 U 组的点连到 U 组的点。

second . 二分图匹配：

首先了解二分图匹配（来自 OIwiki）：

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

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

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

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

啥意思？

当年的我看见这条定义觉得同样很懵。

那我们不管普通的图，只考虑二分图。

其实就是：

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

匹配的大小为边的数量。

应该清楚多了吧。

了解二分图匹配之后，就可以学习二分图最大匹配了。

third . 二分图最大匹配：

顾名思义，就是二分图的所有匹配中边数最多的那个匹配。

OI wiki 同样给出定义：

假设图有 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：

vector 存边，深搜跑算法，重新连接的条件很重要。

#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 级学长课件。