AcWing 4298. 搭档
原题链接
困难
匈牙利算法
解题思路
这道题其实直接把模板默写下来就好,但是需要先建立一个符合条件的邻接表
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110, M = 1e4+10;
int e[M],ne[M],h[M],a[N],b[N],match[N],idx,n,m;
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 != -1; 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()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
cin >> m;
for(int i = 1; i <= m; i ++) cin >> b[i];
memset(h,-1,sizeof h);
//建立邻接表
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
if(abs(a[i] - b[j]) <= 1)
add(i, j);
int ans = 0;
for(int i = 1; i <= n; i ++)
{
memset(st,false,sizeof st);
if(find(i)) ans++;
}
return cout << ans, 0;
}