sicily 1192 二分匹配

//求二分图最大独立集，点之间无边
//先求最大匹配，剩下的点之间不可能有边，再加上匹配数(每对匹配只取一个人)即可
//如果剩下的点中，男的与匹配点中女的有边，就取该匹配的男点
//不可能出现不在匹配中的男女两点同时与同一匹配边有边，因为这样会导致增广
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;struct Person
{int high;char music[101];char sport[101];int nxt[501],m;bool get;int _in;
}B[501],G[501];bool couple( int i, int j )
{if( abs( B[i].high - G[j].high ) > 40 )           return false;if( strcmp( B[i].music, G[j].music ) != 0 ) return false;if( strcmp( B[i].sport, G[j].sport ) == 0 ) return false;return true;
}
int n, t;
int s[501];
int high;
char str[2];
bool _vis[501];
int ymatch[501];
int x = 0, y = 0;
bool find( int xx )
{for( int i = 0;i < B[xx].m;i++ ){int y = B[xx].nxt[i];if( _vis[y] ) continue;_vis[y] = true;if( ymatch[y] == -1 || find( ymatch[y] ) ){ymatch[y] = xx;return true;}}return false;
}
int Pair( )
{int result = 0;memset( ymatch,-1,sizeof(ymatch) );for( int i = 0;i < x;i++ ){memset( _vis,false,sizeof(_vis) );if( find( i ) ) result++;}return result;
}int main()
{scanf( "%d",&t );while( t-- ){scanf( "%d",&n );x = y = 0;for( int i = 0;i < n;i++ ){s[i] = i;B[i].m = 0;scanf( "%d%s",&high,str );if( str[0] == 'M' ){B[x].high = high;scanf( "%s%s",B[x].music,B[x].sport );x++;}else{G[y].high = high;scanf( "%s%s",G[y].music,G[y].sport );y++;}}for( int i = 0;i < x;i++ ){for( int j = 0;j < y;j++ ){if( couple( i,j ) ){B[i].nxt[B[i].m++] = j;}}}printf( "%d\n",n - Pair( ) );}
}