题目链接：
Poj 2289 Jamie's Contact Groups
题目描述：
给出n个人的名单和每个人可以被分到的组，问将n个人分到m个组内，并且人数最多的组人数要尽量少，问人数最多的组有多少人？
解题思路：
二分图多重匹配相对于二分匹配来说不再是节点间的一一对应，而是Xi可以对应多个Yi。所以我们就需要一个限制(Xi最多匹配几个Yi)。当Yi需要匹配Xi的时候，Xi的匹配未到上限，直接匹配，否则进行增广路。其实是二分图多重匹配的模板题，再套一个二分枚举最多组的人数就OK咯。下面就上板子啦。
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = ;
int n, m, mid, maps[maxn][];
int vis[], used[][maxn], link[];
bool Find (int u)
{
for (int i=; i<m; i++)
{
if (maps[u][i] && !vis[i])
{
vis[i] = ;
if (link[i]< mid)
{//没达到上限
used[i][link[i] ++] = u;
return true;
}
for (int j=; j<link[i]; j++)
if (Find(used[i][j]))
{//达到上限，求增广路
used[i][j] = u;
return true;
}
}
}
return false;
}
int hungry ()
{
memset (link, , sizeof(link));
for (int i=; i<n; i++)
{
memset (vis, , sizeof(vis));
if (!Find(i))
return false;
}
return true;
}
int main ()
{
while (scanf("%d %d", &n, &m), n||m)
{
char name[], ch;
memset (maps, , sizeof(maps));
for (int i=; i<n; i++)
{
scanf ("%s%c", name, &ch);
while (ch != '\n')
{
int v;
scanf ("%d%c", &v, &ch);
maps[i][v] = ;
}
}
int left = , right = n;
while (left < right)
{//二分枚举上限
mid = (left + right)/;
if (hungry())
right = mid;
else
left = mid + ;
}
printf ("%d\n", right);
}
return ;
}