[洛谷P3386] [模板] 二分图匹配 (匈牙利算法)

时间:2022-08-14 20:08:08

题目传送门

毒瘤出题人zzk出了个二分图匹配的题(18.10.04模拟赛T2),逼我来学二分图匹配。

网络流什么的llx讲完之后有点懵,还是匈牙利比较好理解(绿与被绿)。

对于左边的点一个一个匹配,记录右边哪个点跟左边的i匹配:cp[i]

如果还没有配对,就直接配上。

如果已经有匹配了,每次dfs找增广路(看看能不能换一下),如果成功,那么匹配数增加一。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,m,ec,ans;
int e[][];
int cp[];
int used[]; int dfs(int p)
{
for(int i=;i<=m;i++)
{
if(!used[i]&&e[p][i])
{
used[i]=;
if(!cp[i]||dfs(cp[i]))
{
cp[i]=p;
return ;
}
}
}
return ;
} void hungary()
{
ans=;
for(int i=;i<=n;i++)
{
memset(used,,sizeof(used));
if(dfs(i))ans++;
}
} int main()
{
scanf("%d%d%d",&n,&m,&ec);
for(int i=;i<=ec;i++)
{
int a,b;
scanf("%d%d",&a,&b);
e[a][b]=;
}
hungary();
printf("%d",ans);
return ;
}