hdu 1669 Jamie's Contact Groups

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn=1010;
const int maxm=510;

int bmap[maxn][maxm],cy[maxm][maxn],bmask[maxm],vcy[maxm],n,m,limit;
char s[2000];

bool findpath(int u)
{
    for(int i=0;i<m;i++)
    {
        if(bmap[u][i]&&!bmask[i])
        {
            bmask[i]=1;
            if(vcy[i]<limit)
            {
                cy[i][vcy[i]++]=u;
                return true;
            }
            for(int j=0;j<vcy[i];j++)
            {
                if(findpath(cy[i][j]))
                {
                    cy[i][j]=u;
                    return true;
                }
            }
        }
    }
    return false;
}

bool mulmatch()
{
    memset(vcy,0,(m+5)*sizeof(int));
    for(int i=0;i<n;i++)
    {
        memset(bmask,0,sizeof(bmask));
        if(!findpath(i)) return false;
    }
    return true;
}

int main()
{
    while(scanf("%d %d",&n,&m),n+m)
    {
        getchar();
        memset(bmap,0,sizeof(bmap));
        memset(cy,0,sizeof(cy));
        memset(s,0,sizeof(s));
        for(int i=0;i<n;i++)
        {
            gets(s);
            int len=strlen(s);
            int ret=0;
            int t;
            for(t=0;t<len;t++)
            {
                if((s[t]>='a'&&s[t]<='z')||(s[t]>='A'&&s[t]<='Z')) continue;
                else break;
            }
            t++;
            for(;t<len;t++)
            {
                if(s[t]>='0'&&s[t]<='9')
                {
                    ret=ret*10+s[t]-'0';
                    if(t+1==len)
                        bmap[i][ret]=1;
                }
                else if(s[t]==' ')
                {
                    bmap[i][ret]=1;
                    ret=0;
                }
            }
            memset(s,0,sizeof(s));
        }
        int l=1,r=n+1,ans=0;
        while(l<r)
        {
            limit=(l+r)>>1;
            if(mulmatch())
                ans=limit,r=limit;
            else l=limit+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}