二分图匹配

  一道超级无敌宇宙可爱的算法。

  我就说几个需要注意的地方: 每一次需要 f l g 防止死循环,并且在return 1之前,别忘了先把情人关系确定下来~(感觉这个最重要)

  下面是代码:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,e,ans;
int mp[1005][1005],folw[1005],flg[1005];
int find(int x)
{
    for(int i=1; i<=m; i++)
        if(mp[x][i] && !flg[i] )
        {
            flg[i]=1;
            if( find(folw[i])|| !folw[i])
            {
                folw[i]=x;
                return 1;
            }
        }
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1; i<=e; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(v>m||u>n) continue;
        mp[u][v]=1;
    }
    for(int i=1; i<=n; i++)
    {
        memset(flg,0,sizeof(flg));
        if(find(i)) ans++;
    }
    printf("%d",ans);
    return 0;
}

 

上一篇:P2219 [HAOI2007]修筑绿化带(二维单调队列)


下一篇:1013 Battle Over Cities