地址
给定一个二分图, 其中左半部包含 n1n1 个点(编号 1~n1n1), 右半部包含 n2n2 个点(编号 1~n2n2), 二分图共包含 m 条边.
数据保证任意一条边的两个端点都不可能在同一部分中.
请你求出二分图的最大匹配数.
二分图的匹配: 给定一个二分图 G, 在 G 的一个子图 M 中, M 的边集 {E} 中的任意两条边都不依附于同一个顶点, 则称 M 是一个匹配.
二分图的最大匹配: 所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配, 其边数即为最大匹配数.
输入格式
第一行包含三个整数 n1n1, n2n2 和 mm.
接下来 m 行, 每行包含两个整数 u 和 v, 表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边.
输出格式
输出一个整数, 表示二分图的最大匹配数.
数据范围
1≤n1,n2≤5001≤n1,n2≤500,
1≤u≤n11≤u≤n1,
1≤v≤n21≤v≤n2,
1≤m≤105
输入样例:
- 2 2 4
- 1 1
- 1 2
- 2 1
- 2 2
输出样例:
2
解法
二分图最大匹配的模板
左右两边的点 我们只需要关注一边的点即可
以左边点为例
第一个点选取第一个可连接的右边的点 然后看第二个点
如果两点的连接的右边的点有冲突, 则其中一个点尝试选择其他可连接的右边的点
如果上述过程全部执行完 所有点均找到可以匹配的右边的点 或者无其他选择 则结束
代码
- #include <iostream>
- #include <vector>
- #include <memory.h>
- using namespace std;
- const int N = 510;
- const int M = 100010;
- int n1, n2, m;
- int match[N];
- bool st[N];
- vector<int> v[2*N];
- int find(int x)
- {
- for (int i = 0; i <v[x].size(); i++) {
- int j = v[x][i];
- if (!st[j]) {
- st[j] = true;
- if (match[j] == 0 || find(match[j]))
- {
- match[j] = x;
- return true;
- }
- }
- }
- return false;
- }
- int main()
- {
- cin>> n1>> n2>> m;
- while (m--) {
- int a, b;
- scanf("%d%d",&a,&b);
- //cin>> a>> b;
- v[a].push_back(b);
- }
- int res = 0;
- for (int i = 1; i <= n1; i++) {
- memset(st, false, sizeof(st));
- if (find(i)) res++;
- }
- //cout << res << endl;
- printf("%d\n",res);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3344575.html