hdu 1669(이분 도 다 중 일치+이분 매 거)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1669
제목:주소록 에 N 명 이 있 습 니 다.모든 사람 이 여러 group 에 속 할 수 있 습 니 다.현재 이 사람들 을 m 그룹 으로 나 누고 각 그룹의 최대 인원 을 max 로 설정 하여 이 최소 의 최대 치 를 구 해 야 합 니 다.
문제 풀이 사고방식:이 문 제 를 해결 하기 전에 먼저 이분 도의 다 중 일치 문 제 를 분명히 해 야 한다.
2 분 그림 의 최대 일치 에서 각 점 은 최대 한 개의 일치 변 과 만 연 결 될 수 있 습 니 다.그러나 우 리 는 이러한 문 제 를 자주 발생 합 니 다.즉,2 분 그림 의 일치 점 은 여러 개의 일치 변 과 연 결 될 수 있 지만 상한 선 이 있 습 니 다.또는 n 은 점 i 가 최대 몇 개의 일치 변 과 연 결 될 수 있 는 지 를 나타 냅 니 다.
해결 방법:헝가리 알고리즘 개선
1.G={X,Y 에서;E}에서 초기 일치 치 M 을 가 져 와 상한 선 하한 선 을 설정 합 니 다.
2.최대 제한 n 에 대해 2 점 매 칭 을 합 니 다.
3.x 가 모두 M 에 일치 하면 2 로 전환 할 수 있 습 니 다.그렇지 않 으 면 yi 와 일치 하 는 수량 이 n 보다 적 으 면 xi,yi 와 일치 합 니 다.
4.만약 에 yi 매 칭 이 상한 선 에 도달 하면 yi 에서 하나의 요 소 를 선택 하여 확대 하고 위 치 를 양보 할 수 있다 면 xi,yi 와 일치 하여 2 로 전환 합 니 다.
여 기 는 완전히 하나의 템 플 릿 입 니 다.먼저 2 분 으로 최대 인원 을 매 거 한 다음 에 헝가리 알고리즘 으로 만족 여 부 를 판단 하면 됩 니 다.

#include
#include
#include
using namespace std;

const int maxn = 1005;
int n,m,max_cap,g[maxn][maxn];
int link[maxn][maxn],num[maxn];
bool vis[maxn];
char str[maxn];

bool dfs(int u)
{
	for(int i = 0; i < m; i++)
	{
		if(g[u][i] > 0 && vis[i] == false)
		{
			vis[i] = true;
			if(num[i] < max_cap)
			{
				link[i][num[i]++] = u;
				return true;
			}
			for(int j = 0; j < num[i]; j++)
			{
				if(dfs(link[i][j]))
				{
					link[i][j] = u;
					return true;
				}
			}
		}
	}
	return false;
}

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

int getDigit(int s,int e)
{
	int ans = 0;
	for(int i = s; i <= e; i++)
		ans = ans * 10 + str[i] - '0';
	return ans;
}

int main()
{
	while(cin >> n >> m,n+m)
	{
		memset(g,0,sizeof(g));
		for(int i = 0; i < n; i++)
		{
			cin >> str;
			gets(str);
			int len = strlen(str);
			for(int j = 1,k; j < len; j = k + 1)
			{
				k = j;
				while(str[k] != ' ' && str[k] != '\0') k++;
				g[i][getDigit(j,k-1)] = 1;
			}
		}
		int l = 1,r = n,mid,ans;
		while(l <= r)
		{
			mid = (l + r) >> 1;
			if(Max_Match(mid))
			{
				ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		printf("%d
",ans);
	}
	return 0;
}