2771.cpp

这些是我到目前在PKU上做出的题目

#include <memory.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define LEFT_MAX 501
#define RIGHT_MAX 501
#define STR_MAX 101

bool useif[RIGHT_MAX];
int link[RIGHT_MAX];
int left_num=0,right_num=0;
int boy_height[LEFT_MAX];
char boy_music[LEFT_MAX][STR_MAX],boy_sport[LEFT_MAX][STR_MAX]; 
int girl_height[RIGHT_MAX];
char girl_music[RIGHT_MAX][STR_MAX],girl_sport[RIGHT_MAX][STR_MAX];
int array[LEFT_MAX][RIGHT_MAX];

bool can(int t)
{
 int i;
 
 for(i=0;i<right_num;i++)
 {
        if(array[t][i]==-1)
        {
            if(strcmp(boy_music[t],girl_music[i])==0 && abs(boy_height[t]-girl_height[i])<=40 && strcmp(boy_sport[t],girl_sport[i])!=0)
                array[t][i]=1;
            else
                array[t][i]=0;
        }
		if(!useif[i] && array[t][i])
		{
			useif[i]=true;
			if(link[i]==-1 || can(link[i]))
			{
				link[i]=t;
				return true;
			}
		}

 }
 return false;
}

int main()
{
	int i,j,num,count,person,temp_height;
	char c;
	scanf("%d",&count);
	for(j=0;j<count;j++)
	{
 		num=0;       
		left_num=0,right_num=0;
		memset(link,0xFF,sizeof(link));
		memset(array,0xFF,sizeof(array));
		memset(useif,0,sizeof(useif));
		memset(boy_height,0,sizeof(boy_height));
		memset(girl_height,0,sizeof(girl_height));
		memset(boy_music,0,sizeof(boy_music));
		memset(girl_music,0,sizeof(girl_music));
		memset(boy_sport,0,sizeof(boy_sport));
		memset(girl_sport,0,sizeof(girl_sport));		
		scanf("%d",&person);
		for(i=0;i<person;i++)
		{
			scanf("%d %c",&temp_height,&c);
			if(c=='M')
			{
				boy_height[left_num]=temp_height;
				scanf("%s",boy_music+left_num);
				scanf("%s",boy_sport+left_num);
				left_num++;
			}
			else
			{
				girl_height[right_num]=temp_height;
				scanf("%s",girl_music+right_num);
				scanf("%s",girl_sport+right_num);
				right_num++;
			}

   
		}
		for(i=0;i<left_num;i++)
		{
			memset(useif,0,sizeof(useif));
			if(can(i))
				num++;
		}
		printf("%d\n",person-num);
	}
 return 0;
}