2210897_wa.c

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

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

struct node
{
	int h;
	char music[101];
	char sport[101];
}boy[501],girl[501];

int bn, gn;
int b[501], link[501];
int g[501][501];

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;
}

int find(int a)
{
	int i;

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

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

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