NVIDIA RTX wallpaper
816 字
4 分钟
【OI考古】图论 | 二分图匹配
先决条件
二分图
二分图的匹配
增广路
对于一个二分图 ,对于一个匹配 ,若 ,则 间任意路 是一条增广路。
显然,在该增广路上构造包含 的匹配,其余匹配不变,所得的图 的新匹配 匹配数必大于 。重复寻找这样的增广路,经过有限次操作后,必能最大化 的匹配数。
模板题 - 洛谷 P3386 | 【模板】二分图最大匹配
题目描述
题目描述 给定一个二分图,其左部点的个数为 ,右部点的个数为 ,边数为 ,求其最大匹配的边数。
左部点从 至 编号,右部点从 至 编号。
输入格式
输入的第一行是三个整数,分别代表 和 。
接下来 行,每行两个整数 ,表示存在一条连接左部点 和右部点 的边。
输出格式
输出一行一个整数,代表二分图最大匹配的边数。
输入输出样例
输入1
1 1 1
1 1
输出1
1
输入2
1 1 1
1 1
输出2
1
说明/提示
数据规模与约定 对于全部的测试点,保证:
- 。
- 。
- , 。
不保证给出的图没有重边。
解决方案
思路
具体到代码上,假设已经匹配好了部分顶点(没有匹配任何顶点也行),考虑当前的某个顶点 ,只需要验证能不能找到一种匹配,让另一个顶点和 匹配,总匹配数+1
就行,即要尝试寻找以 为起点的增广路。
对于与它邻接的某个顶点 ,如果 没有和任何顶点匹配,则 就是一条增广路,匹配数+1
;如果 已经和其他某个顶点 匹配好了,那么尝试取消 间的匹配,然后寻找以 为起点的增广路。
这个过程是递归进行的,如果持续递归,最终却没有找到某个没有匹配的顶点 作为增广路的终点,则寻找以 为起点的增广路失败,否则寻找增广路成功,匹配数+1
。
对于这题来说,建图的时候顶点不能重复,所以右部顶点编号全部由输入数据加 得到
代码
#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;
}
【OI考古】图论 | 二分图匹配
https://blog.vonbrank.com/posts/oi-graph-theory-bigraph-match/