2210968_ac_515ms_1208k.c

北大大牛代码 1240道题的原代码 超级权威

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

struct node
{
	int h;
	char music[111];
	char sport[111];
}boy[511],girl[511];

int bn, gn;
int b[511], link[511], c[511];
int g[511][511];

int check(int i,int j)
{
	if(abs(boy[i].h-girl[j].h)>40)
		return 0;
	if(strcmp(boy[i].music,girl[j].music)!=0)
		return 0;
	if(strcmp(boy[i].sport,girl[j].sport)==0)
		return 0;
	return 1;
}

int find(int a)
{
	int i;

	for(i = 1; i<= gn; i++)
	{
		if(g[a][i]&&!b[i])
		{
			b[ i ]=1;
		        if(!link[i]||find(link[i]))
			{
				link[i]=a;
				c[a] = i;
				return 1;
			}
		}
	}
	return 0;
}
void input()
{
	int t, p, i, j, h, ans;
	char tmp[2], m[111], s[111];

	scanf("%d",&t);
	while(t--)
	{
		memset(g,0,sizeof(g));
		memset(link,0,sizeof(link));
		memset(c,0,sizeof(c));
		scanf("%d",&p);
		bn = gn = ans = 0;
		for(i = 0; i < p; i++)
		{
			scanf("%d%s%s%s",&h,tmp,m,s);
			if(strcmp(tmp,"M")==0)
			{
				bn++;
				boy[bn].h = h;
				strcpy(boy[bn].music,m);strcpy(boy[bn].sport,s);
				
			}
			else
			{
				gn++;
				girl[gn].h = h;
				strcpy(girl[gn].music,m);strcpy(girl[gn].sport,s);
			}
		}
		for(i = 1; i <= bn; i++)
			for(j = 1; j <= gn; j++)
			{
				if(check(i,j))
					g[i][j]  = 1;
			}
		for(i = 1; i <= bn; i++)
		{
			if(!c[i])
			{
				memset(b,0,sizeof(b));
				ans+=find(i);
			}
		}
		printf("%d\n",p-ans);
	}
}

int main()
{
	input();
	return 1;
}