题目:给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数。
解法:匈牙利算法。(以前我总是不记得......)实质上应该有贪心的思想,每次都尽量匹配,找到能和自己匹配的也尽量让它们匹配。若对方已有匹配的对象,就让那个对象尽量调整来使自己这对能凑起来。而要注意,每次问过的对象就不要再问了,也就是不要让它的对象总是换来换去......
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int N=,M=;
int n,m,e;
int vis[N][N];
int ask[M],cp[M]; bool ffind(int x)
{
for (int i=;i<=m;i++)
if (vis[x][i])
{
if (ask[i]) continue;
ask[i]=;
if (!cp[i]||ffind(cp[i]))
{cp[i]=x;return true;}
}
return false;
}
void getmatch()
{
int ans=;
memset(cp,,sizeof(cp));
for (int i=;i<=n;i++)
{
memset(ask,,sizeof(ask));
if (ffind(i)) ans++;
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d%d",&n,&m,&e);
for (int i=;i<=e;i++)
{
int x,y;
scanf("%d%d",&x,&y);
vis[x][y]=;
}
getmatch();
return ;
}