AcWing 861. 找对象算法👦 🧡 👩
原题链接
简单
作者:
Jacky.C
,
2021-02-04 17:48:37
,
所有人可见
,
阅读 1605
恋爱攻略尽在代码中......
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
// 找对象匹配算法👦 🧡 👩
const int N = 550, M = 100010;
int h[N], val[M], ne[M], idx;
int match[N];
bool vis[N];
void add(int a, int b)
{
val[idx] = b;
ne[idx] = h[a];
h[a]= idx++;
}
bool find(int x)
{
for(int i = h[x]; i != -1; i = ne[i]){ // 枚举所有心仪妹子
int v = val[i]; // 获取妹子编号
if(!vis[v]){ // 妹子还没预定
vis[v] = 1; // 预定一下(o゜▽゜)o 她
if(!match[v] || find(match[v])){ // 妹子单身 或者 妹子的现男友还有备胎
match[v] = x; // 果断勾搭 或者 绿了她现男友💚
return 1; // 成功找到妹子
}
}
}
return 0; // 相亲失败😢
}
int main()
{
int n1,n2,m;
cin>>n1>>n2>>m;
memset(h, -1, sizeof h);
for(int i = 0; i<m; i++) {
int a,b;
cin>>a>>b;
add(a, b);
}
int res = 0;
for(int i = 1; i<=n1; i++){
memset(vis, 0, sizeof vis);
if(find(i)) res++;
}
cout<<res<<endl;
return 0;
}
图论一刷 自己在csdn上写了一下二分图查找最大匹配的博文
如果st数组看不懂或者啥的可以去看看,交流交流也行
https://blog.csdn.net/WJPnb1/article/details/126332263
莫名可爱
我这份代码有问题,但我觉得跟你的没区别啊
666