【OI考古】图论 | 二分图匹配

先决条件

二分图

二分图的匹配

增广路

对于一个二分图 $G$ ，对于一个匹配 $M$ ，若 $\exist \ u, v \notin M$ ，则 $u, v$ 间任意路 $u, v_1, v_2, \dots , v_n , v$ 是一条增广路。

显然，在该增广路上构造包含 $uv_1, v_nu$ 的匹配，其余匹配不变，所得的图 $G$ 的新匹配 $M'$ 匹配数必大于 $M$ 。重复寻找这样的增广路，经过有限次操作后，必能最大化 $M$ 的匹配数。

模板题 - 洛谷 P3386 | 【模板】二分图最大匹配

题目描述

题目描述
给定一个二分图，其左部点的个数为 $n$ ，右部点的个数为 $m$ ，边数为 $e$ ，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

输入格式

输入的第一行是三个整数，分别代表 $n，m$ 和 $e$ 。

接下来 $e$ 行，每行两个整数 $u, v$ ，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

输出格式

输出一行一个整数，代表二分图最大匹配的边数。

输入输出样例

输入`1`

1
2

1 1 1
1 1

输出`1`

输入`2`

1
2

1 1 1
1 1

输出`2`

说明/提示

数据规模与约定
对于全部的测试点，保证：

$1 \leq n, m \leq 500$ 。
$1 \leq e \leq 5 \times 10^4$ 。
$1 \leq u \leq n$ ， $1 \leq v \leq m$ 。

不保证给出的图没有重边。

解决方案

思路

具体到代码上，假设已经匹配好了部分顶点（没有匹配任何顶点也行），考虑当前的某个顶点 $u$ ，只需要验证能不能找到一种匹配，让另一个顶点和 $u$ 匹配，总匹配数+1就行，即要尝试寻找以 $u$ 为起点的增广路。

对于与它邻接的某个顶点 $v$ ，如果 $v$ 没有和任何顶点匹配，则 $uv$ 就是一条增广路，匹配数+1；如果 $v$ 已经和其他某个顶点 $w$ 匹配好了，那么尝试取消 $v, w$ 间的匹配，然后寻找以 $w$ 为起点的增广路。

这个过程是递归进行的，如果持续递归，最终却没有找到某个没有匹配的顶点 $t$ 作为增广路的终点，则寻找以 $u$ 为起点的增广路失败，否则寻找增广路成功，匹配数+1。

对于这题来说，建图的时候顶点不能重复，所以右部顶点编号全部由输入数据加 $n$ 得到

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 505;
const int maxe = 50050;
int n, m, e, cnt, ans;
bool used[maxn << 1];
int head[maxn << 1], girl[maxn << 1];
struct Node
{
    int to, next;
} G[maxe << 1];
void addedge(int u, int v)
{
    ++cnt;
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt;
}
bool find(int u)
{
    for (int j = head[u]; j; j = G[j].next)
    {
        int v = G[j].to;
        if (!used[v])
        {
            used[v] = true;
            if (girl[v] == 0 || find(girl[v]))
            {
                girl[v] = u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d %d %d", &n, &m, &e);
    for (int i = 1; i <= e; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        addedge(u, n + v);
        addedge(n + v, u);
    }
    for (int i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (find(i))
            ans++;
    }
    printf("%d", ans);
    return 0;
}