Description
Input
Output
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个组。问你将n个人分到组中，且每个人只能分到一个组内，最大组（组内人数最多）的最小值是多少。
解题思路：多重匹配。这是一对多的情况。很明显是多重匹配，但是匹配次数却没有，而是让求的结果。那我们就枚举匹配次数。如果该匹配次数满足条件，记录答案，同时向小逼近，如果不满足，就向大逼近。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
const int maxn = 1010;
int Map[maxn][maxn];
//linker[v][j]表示第j个与Y部的v匹配的是x部的谁
int linker[maxn][maxn], used[maxn];
int mid;
bool dfs(int u,int rn){
for(int v = 1; v <= rn; v++){
if(used[v] || !Map[u][v]){
continue;
}
used[v] = 1;
if(linker[v][0] < mid){ //枚举的匹配次数
linker[v][++linker[v][0]] = u;
return true;
}else{
for(int j = 1; j <= linker[v][0]; j++){
if(dfs(linker[v][j],rn)){
linker[v][j] = u;
return true;
}
}
}
}
return false;
}
bool Hungary(int ln,int rn){
int ret = 0;
for(int i = 0; i <= rn; i++){
linker[i][0] = 0;
}
for(int i = 1; i <= ln; i++){
memset(used,0,sizeof(used));
if(dfs(i,rn)){
ret++;
}
}
if(ln == ret){
return true;
}
return false;
}
int main(){
int n,m;
char str[5000];
while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){
memset(Map,0,sizeof(Map));
getchar();
for(int i = 1; i <= n; i++){
gets(str);
int len = strlen(str);
int v = 0, flag = 1;
for(int j = 0; j <= len; j++){
if(str[j] >= ‘0‘&& str[j] <= ‘9‘){
v = v*10 + str[j]-‘0‘;
flag = 0;
}else{
if(flag) continue;
else{
Map[i][v+1] = 1; v = 0;
}
}
}
}
int l = 1, r = n;
while(l < r){
mid = (l+r)/2;
if(Hungary(n,m)){
r = mid;
}else{
l = mid + 1;
}
}
printf("%d\n",r);
}
return 0;
}
POJ 2289——Jamie's Contact Groups——————【多重匹配、二分枚举匹配次数】
原文：http://www.cnblogs.com/chengsheng/p/4961210.html