题目链接：
Poj 2289 Jamie's Contact Groups
题目描述：
给出n个人的名单和每个人可以被分到的组，问将n个人分到m个组内，并且人数最多的组人数要尽量少，问人数最多的组有多少人？
解题思路：
二分图多重匹配相对于二分匹配来说不再是节点间的一一对应，而是Xi可以对应多个Yi。所以我们就需要一个限制(Xi最多匹配几个Yi)。当Yi需要匹配Xi的时候，Xi的匹配未到上限，直接匹配，否则进行增广路。其实是二分图多重匹配的模板题，再套一个二分枚举最多组的人数就OK咯。下面就上板子啦。
1 #include <vector> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1010; 9 int n, m, mid, maps[maxn][505]; 10 int vis[505], used[505][maxn], link[505]; 11 bool Find (int u) 12 { 13 for (int i=0; i<m; i++) 14 { 15 if (maps[u][i] && !vis[i]) 16 { 17 vis[i] = 1; 18 if (link[i]< mid) 19 {//没达到上限 20 used[i][link[i] ++] = u; 21 return true; 22 } 23 for (int j=0; j<link[i]; j++) 24 if (Find(used[i][j])) 25 {//达到上限，求增广路 26 used[i][j] = u; 27 return true; 28 } 29 } 30 } 31 return false; 32 } 33 int hungry () 34 { 35 memset (link, 0, sizeof(link)); 36 for (int i=0; i<n; i++) 37 { 38 memset (vis, 0, sizeof(vis)); 39 if (!Find(i)) 40 return false; 41 } 42 return true; 43 } 44 int main () 45 { 46 while (scanf("%d %d", &n, &m), n||m) 47 { 48 char name[20], ch; 49 memset (maps, 0, sizeof(maps)); 50 for (int i=0; i<n; i++) 51 { 52 scanf ("%s%c", name, &ch); 53 while (ch != ' ') 54 { 55 int v; 56 scanf ("%d%c", &v, &ch); 57 maps[i][v] = 1; 58 } 59 } 60 int left = 0, right = n; 61 while (left < right) 62 {//二分枚举上限 63 mid = (left + right)/2; 64 if (hungry()) 65 right = mid; 66 else 67 left = mid + 1; 68 } 69 printf ("%d ", right); 70 } 71 return 0; 72 }