#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 510
struct Stu
{
int height;
char sex[5];
char music[110];
char sport[110];
};
Stu p[N];
bool map[N][N];
int match[N];
bool visite[N];
int id[N];
int n,m,t;
bool isok( Stu const& a, Stu const& b )
{
return abs( a.height- b.height )<= 40 && strcmp(a.music,b.music )== 0 && strcmp(a.sport,b.sport )!= 0 ;
}
int abs( int const& a )
{
return a> 0? a: -a;
}
void build()
{
n= 0, m= 0;
memset( map, false, sizeof(map) );
memset( match, -1, sizeof(match) );
for( int i= 0; i< t; ++i )
{
if( p[i].sex[0]== 'M' ) id[i]= n++;
else id[i]= m++;
}
for( int i= 0; i< t; ++i )
for( int j= 0; j< t; ++j )
if( p[i].sex[0]== 'M' && p[j].sex[0]== 'F' && isok( p[i], p[j] ) )
map[ id[i] ][ id[j] ]= true;
}
bool dfs( int p )
{
for( int i= 0; i< m; ++i )
if( !visite[i] && map[p][i] )
{
visite[i]= true;
int t= match[i];
match[i]= p;
if( t== -1 || dfs(t) ) return true;
match[i]= t;
}
return false;
}
int Match()
{
int ret= 0;
for( int i= 0; i< n; ++i )
{
memset( visite, false, sizeof(visite) );
if( dfs(i) ) ret++;
}
return ret;
}
int main()
{
int test;
scanf("%d", &test );
while( test-- )
{
scanf("%d", &t );
for( int i= 0; i< t; ++i )
scanf("%d %s %s %s", &p[i].height, p[i].sex, p[i].music, p[i].sport );
build();
printf("%d\n", t- Match() );
}
return 0;
}
posted on 2008-11-05 12:05
Darren 閱讀(299)
評論(1) 編輯 收藏 引用