HDU 1669 -- POJ 2289 Jamie's Contact Groups(二分+二分图多重匹配)

// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define maxn 1010
// #define maxm 505
using namespace std;
struct Link{
	int cnt;
	int k[maxn];
}link[maxn];
bool maps[maxn][maxn];
bool vis[maxn];
int n,m,xx;
char str[20],ch;

void init(){
	memset(maps,false,sizeof(maps));
}

bool dfs(int u, int limit){
	for(int i=1;i<=m;i++){
		if(vis[i] == false && maps[u][i] == true){
			vis[i] = true;
			if(link[i].cnt < limit){
				link[i].k[ ++ link[i].cnt ] = u;
				return true;
			}
			for(int j=1;j<=link[i].cnt;j++){
				if(dfs(link[i].k[j], limit)){
					link[i].k[j] = u;
					return true;
				}
			}
		}
	}
	return false;
}

bool solve(int limit){
	memset(link,0,sizeof(link));
	for(int i=1;i<=n;i++){
		memset(vis,false,sizeof(vis));
		if(!dfs(i, limit)) return false;
	}
	return true;
}

int main()
{
	while(~scanf("%d%d",&n,&m)){
		if(n == 0 && m == 0) break;
		init();
		for(int i=1;i<=n;i++){
			scanf("%s",str);
			while(1){
				scanf("%d%c",&xx, &ch);
				maps[i][xx + 1] = true;
				if(ch == '\n') break;
			}
		}
		int l = 1, r = n, mid, ans = n;
		while(l <= r){
			mid = (l + r) >> 1;
			if(solve(mid)){
				r = mid - 1;
				ans = mid;
			}
			else{
				l = mid + 1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}