该题反过来想：将所有可能发生恋爱关系的男女配对，那么可以带出去的人数应该等于这个二分图的最大独立集 先要做一下预处理，把不符合要求的双方先求出来, company[i][j]表示i、j四个标准都不符合，即他们可能会成为伴侣。
这里要注意因为x、y集合都是0~n-1，左右对称，所以求最大点独立集的点的个数时，最后还要/2。
接下来就是求最大独立集的点的个数。
最大点独立集+最小点覆盖=点的个数 独立集：在集合中的任意两点都不相邻，即两点间不存在边
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std; const int maxnx=;
const int maxny=; int company[maxnx][maxny]; //company[i][j]=1表示i、j四个条件全满足，有可能成为伴侣
int used[maxny];
int cnt,t,n,k;
int matchx[maxny]; struct Person{
int height;
int sex; //0代表女，1代表男
char music[],sports[];
}pupil[]; bool dfsfind(int k){
for(int i=;i<n;i++){
if(company[k][i] && !used[i]){
used[i]=;
if(matchx[i]==- || dfsfind(matchx[i])){
matchx[i]=k;
return true;
}
}
}
return false;
} int hungry(){
cnt=;
memset(matchx,-,sizeof(matchx));
for(int j=;j<n;j++){
memset(used,,sizeof(used));
if(dfsfind(j)){
cnt++;
}
}
return cnt; } void deal(){
Person p1,p2;
for(int i=;i<n;i++){
for(int j=i;j<n;j++){
p1=pupil[i];
p2=pupil[j];
if((abs(p1.height-p2.height)<=)&&(p1.sex!=p2.sex)&&(strcmp(p1.music,p2.music)==)&&(strcmp(p1.sports,p2.sports)!=)){
company[i][j]=;
company[j][i]=;
}
}
} }
int main()
{
char s1[];
scanf("%d",&t);
for(int q=;q<t;q++){
scanf("%d",&n);
memset(company,,sizeof(company)); for(int i=;i<n;i++){
scanf("%d%s%s%s",&pupil[i].height,s1,pupil[i].music,pupil[i].sports);
if(s1[]=='F')
pupil[i].sex=;
else
pupil[i].sex=;
}
deal(); int ans=(*n-hungry())/;
printf("%d\n",ans); }
return ;
}