POJ2289 Jamie's Contact Groups(二分图多重匹配+二分)

Description

Jamie is a very popular girl and has quite a lot of friends, so she
always keeps a very long contact list in her cell phone. The contact
list has become so long that it often takes a long time for her to
browse through the whole list to find a friend’s number. As Jamie’s
best friend and a programming genius, you suggest that she group the
contact list and minimize the size of the largest group, so that it
will be easier for her to search for a friend’s number among the
groups. Jamie takes your advice and gives you her entire contact list
containing her friends’ names, the number of groups she wishes to have
and what groups every friend could belong to. Your task is to write a
program that takes the list and organizes it into groups such that
each friend appears in only one of those groups and the size of the
largest group is minimized.

Input

There will be at most 20 test cases. Ease case starts with a line
containing two integers N and M. where N is the length of the contact
list and M is the number of groups. N lines then follow. Each line
contains a friend’s name and the groups the friend could belong to.
You can assume N is no more than 1000 and M is no more than 500. The
names will contain alphabet letters only and will be no longer than 15
characters. No two friends have the same name. The group label is an
integer between 0 and M - 1. After the last test case, there is a
single line `0 0’ that terminates the input.

Output

For each test case, output a line containing a single integer, the
size of the largest contact group.

Sample Input

3 2
John 0 1
Rose 1
Mary 1
5 4
ACM 1 2 3
ICPC 0 1
Asian 0 2 3
Regional 1 2
ShangHai 0 2
0 0

Sample Output

2
2

思路

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

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

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

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

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <set>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
using namespace std;
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;
}