pku2771.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#include <math.h>

typedef struct 
{
	int Hei;
	char Mus[101];
	char Spo[101];
} Person;

Person man[501], woman[501];
int man_N, woman_N;
int st[501][501];
int chk[501];
int match[501];

int Check(int i, int j)
{
	if (abs(man[i].Hei - woman[j].Hei) > 40)
	{
		return 0;
	}
	if (strcmp(man[i].Mus, woman[j].Mus))
	{
		return 0;
	}
	if (strcmp(man[i].Spo, woman[j].Spo) == 0)
	{
		return 0;
	}
	return 1;
}

void pre()
{
	int i, j;
	memset(st, 0, sizeof(st));
	for (i = 0; i < man_N; i++)
	{
		for (j = 0; j < woman_N; j++)
		{
			st[i][j] = Check(i, j);
		}
	}
}

int DFS(int p)
{
	int i, t;
	for (i = 0; i < man_N; i++)
	{
		if (st[i][p] && !chk[i])
		{
			chk[i] = 1;
			t = match[i];
			match[i] = p;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
			match[i] = t;
		}
	}
	return 0;
}

void Solve()
{
	int N, i, ans;
	int hei;
	char sex;
	char mus[101];
	char spo[101];
	man_N = 0;
	woman_N = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d %c %s %s", &hei, &sex, mus, spo);
		if (sex == 'M')
		{
			man[man_N].Hei = hei;
			strcpy(man[man_N].Mus, mus);
			strcpy(man[man_N].Spo, spo);
			man_N++;
		}
		else
		{
			woman[woman_N].Hei = hei;
			strcpy(woman[woman_N].Mus, mus);
			strcpy(woman[woman_N].Spo, spo);
			woman_N++;
		}
	}
	pre();
	ans = 0;
	memset(match, -1, sizeof(match));
	for (i = 0; i < woman_N; i++)
	{
		memset(chk, 0, sizeof(chk));
		ans += DFS(i);
	}
	printf("%d\n", N - ans);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		Solve();
	}
	return 0;
}