AcWing 861. 二分图的最大匹配 匈牙利算法
2024-09-01 05:15:01
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = , M = ;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool find(int x) {
for (int i = h[x]; i != -; i = ne[i]) {//枚举所有看上的
int j = e[i];
if (!st[j]) {//如果没考虑过
st[j] = true;//表示考虑过了
//如果这个妹子还没匹配其他男生 ,或者说虽然已经匹配了,但可以给那个男生找到下家
if (match[j] == || find(match[j])) {
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
scanf("%d%d%d", &n1, &n2, &m);
memset(h, -, sizeof h);
while (m -- ) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
int res = ;//匹配的数量
for (int i = ; i <= n1; i ++ ) {//依次看每个男生
memset(st, false, sizeof st);//先把所以的妹子清空,表示都还没考虑过
if (find(i)) res ++ ;//如果成功过找到,就加一
}
printf("%d\n", res);
return ;
}
最新文章
- 字符串0.在php和js中转换为布尔类型 值是false还是true
- MVVM模式下,ViewModel和View,Model有什么区别
- netbeans设置语言
- Android屏蔽返回键
- svn在linux下的使用(转)
- sap 三代出口(BADI)的查找方法
- spark下统计单词频次
- Eclipse代码风格设置
- 协方差cov
- 为《31天成为IT服务达人》征求正式名字
- 【C语言】超大数乘法运算
- 协同编辑多人word一个小技巧文件
- jQuery – 鼠标经过(hover)事件的延时处理
- ztree树应用
- 关于在Fragment中设置toolbar及菜单的方法
- day_5.12 py 老王开枪demo
- PSFTP用法
- Android 开发工具类 14_ JsonTools
- AndroidStudio安装教程
- python基础的一些知识点