多重匹配

在通讯录中有N个人，每个人能可能属于多个组，现要将这些人分组m组，设各组中的最大人数为max，尽可能的把组分小，求出这些小组里面的人数的最大值

和一般的最大匹配不同的是，二分图的最大匹配是一个点对一个点的匹配，求的是最大有多少个匹配数，而多重匹配的定义是，一个点可以匹配多个点，并且在这道题目里面多了一个限制条件，就是限制一下一个右边的每个点能匹配左边的点的数量。

我们用二分的方法，枚举一下匹配的数量，如果分成总区间的一半可以分，那么就可以继续分下去，往左找，否则往右找

对于代码我们定义： num[MAXM];//右边最大的匹配数 match[v][0]代表当前这个点匹配了多少个 match[v][1,2,3..n]代表第几个匹配的是哪个点

const int N=1000+20;
int n,m;
bool vis[N];
//match[v][0]代表当前这个点匹配的个数
//match[v][1,2,3...n]代表第v个点匹配的是哪个点
int e[N][N],match[N][N];
int num[N];//右边最大的匹配数
bool dfs(int u)
{
    for(int v=0; v<m; v++)
    {
        if(e[u][v]&&!vis[v])
        {
            vis[v]=true;
            if(match[v][0]<num[v])//如果该点还可以继续匹配
            {
                match[v][++match[v][0]]=u;//记录该点匹配的是哪一个点
                return true;
            }
            for(int i=1; i<=num[0]; i++)//遍历一下当前枚举的数
            {
                if(dfs(match[v][i]))//如果能找到增广路
                {
                    match[v][i]=u;
                    return true;
                }
            }
        }
    }
    return false;
}
int query()
{
    mem(match,0);
    int sum=0;
    for(int i=0; i<n; i++)
    {
        mem(vis,0);
        if(dfs(i))sum++;
    }
    return sum;
}
bool judge(int mid)
{
    fill(num,num+n,mid);
    int ans=query();
    if(ans==n)
        return true;
    else
        return false;
}
int main()
{
    string s;
    int x;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        mem(e,0);
        for(int i=0; i<n; i++)
        {
            cin>>s;
            while(getchar()!='\n')
            {
                scanf("%d",&x);
                e[i][x]=1;
            }
        }
        int l=0,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(judge(mid))
                r=mid;
            else
                l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}