先决条件

二分图

二分图的匹配

增广路

对于一个二分图 GG ,对于一个匹配 MM ,若  u,vM\exist \ u, v \notin M ,则 u,vu, v 间任意路 u,v1,v2,,vn,vu, v_1, v_2, \dots , v_n , v 是一条增广路。

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

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

题目描述

题目描述
给定一个二分图,其左部点的个数为 nn ,右部点的个数为 mm ,边数为 ee ,求其最大匹配的边数。

左部点从 11nn 编号,右部点从 11mm 编号。

输入格式

输入的第一行是三个整数,分别代表 nmn,mee

接下来 ee 行,每行两个整数 u,vu, v ,表示存在一条连接左部点 uu 和右部点 vv 的边。

输出格式

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

输入输出样例

输入1
1
2
1 1 1
1 1
输出1
1
1
输入2
1
2
1 1 1
1 1
输出2
1
1

说明/提示

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

  • 1n,m5001 \leq n, m \leq 500
  • 1e5×1041 \leq e \leq 5 \times 10^4
  • 1un1 \leq u \leq n1vm1 \leq v \leq m

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

解决方案

思路

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

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

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

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

代码

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
#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;
}