二分图最大匹配(匈牙利算法Dfs模板)

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 2020
using namespace std;
int n,m,g[maxn][maxn],ans,f[maxn],match[maxn];
int init()
{
int x=;char s;s=getchar();
while(s<''||s>'')s=getchar();
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x;
}
int Dfs(int s)
{
for(int i=;i<=n;i++)
if(g[s][i]&&f[i]==)
{
f[i]=;
if(match[i]==||Dfs(match[i]))
{
match[i]=s;
return ;
}
}
return ;
}
int main()
{
n=init();m=init();
int x,y;
for(int i=;i<=m;i++)
{
x=init();y=init();
g[x][y]=;
}
for(int i=;i<=n;i++)
{
memset(f,,sizeof(f));
ans+=Dfs(i);
}
printf("%d\n",n-ans);
return ;
}
上一篇:51Nod 1090 3个数和为0


下一篇:使用SQLIO测试磁盘性能