hdu2063 基础二分图匹配，安利一篇好文章

写这个题的原因是因为看到了一篇特别好的安利文章然后就统统记下来以防以后忘了匈牙利算法。

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2063

安利文章链接 http://blog.csdn.net/dark_scope/article/details/8880547 谢谢大犇。

就是扫一遍，给每个男生尝试这去找女生如果找不到，让前面已经配对的先断开，再找，如果还是找不到，就过。

真的写的比较好。然后就直接套模板就可以了，实在不懂就看文章吧。

#include <stdio.h>
#include<string.h>
#define manx 505
using namespace std;
bool line[manx][manx];
bool used[manx];
int k,m,n;
int boys[manx];

bool find(int x)
{
    for(int j=1;j<=n;j++)
    {
        if(line[x][j]&&used[j]==0)
        {
            used[j]=1;
            if(boys[j]==0||find(boys[j]))
            {
                boys[j]=x;
                return 1;

            }


        }
    }
    return 0;
}




int main()
{
    while(~scanf("%d",&k))
    {

        if(k==0) break;
        scanf("%d%d",&m,&n);
        for(int i=0;i<manx;i++)
            memset(line[i],0,sizeof(line[i]));
            memset(boys,0,sizeof(boys));
        int a,b;
        for(int i=0;i<k;i++)
        {
            scanf("%d%d",&a,&b);
            line[a][b]=1;

        }
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            memset(used,0,sizeof(used));
            if(find(i)) ans+=1;
        }

        printf("%d\n",ans);
    }
    return 0;
}