题意分析

1. 冲突条件：
   • 定义两个学生$u$和$v$存在冲突当且仅当：
     • 身高差$\leq 40$厘米
     • 性别不同
     • 音乐风格相同
     • 运动不同
   • 目标：选择最多学生使得任意两人无冲突
2. 问题转化：
   • 将学生看作图的顶点，冲突关系看作边
   • 求图的最大独立集（两两无边连接的顶点集）

解题思路

1. 补图构造：
   • 构建补图，其中边表示可以共存的两人
   • 最大独立集 = 补图的最大团
2. 二分图特例：
   • 若能将学生按性别分为两部分，则转为二分图最大匹配问题
3. 近似算法：
   • 对于一般图，使用$Bron-Kerbosch$等算法求最大团

实现步骤

1. 冲突检测：
   • 遍历所有学生对，标记冲突关系
2. 补图构建：
   • 将原图的非冲突关系作为新图的边
3. 求解最大团：
   • 使用回溯法或启发式算法寻找最大完全子图
4. 输出结果：
   • 最大团的大小即为答案

代码实现

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    int h;
    char sex;
    char mus[110];
    char spo[110];
}M[510],F[510];
int n,m,f,mmap[550][550],pre[550],vis[550];
int pd(int i,int j)
{
    if( abs(M[i].h - F[j].h) > 40 )
        return 0;
    if( strcmp(M[i].mus,F[j].mus) )
        return 0;
    if( strcmp(M[i].spo,F[j].spo) == 0 )
        return 0;
    return 1;
}
int dfs(int x)
{
    for(int i=m+1;i<=m+f;i++){
        if(!vis[i]&&mmap[x][i]){
            vis[i]=1;
            if(pre[i]==-1||dfs(pre[i])){
                pre[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,t,h;
    char str[100];
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        m=f=1;
        memset(mmap,0,sizeof(mmap));
        memset(pre,-1,sizeof(pre));
        memset(M,0,sizeof(M));
        memset(F,0,sizeof(F));
        for(i=1;i<=n;i++){
            scanf("%d%s",&h,str);
            if(str[0]=='M'){
                scanf("%s%s",M[m].mus,M[m].spo);
                M[m].h=h;
                M[m++].sex='M';
            }
            else {
                scanf("%s%s",F[f].mus,F[f].spo);
                F[f].h=h;
                F[f++].sex='F';
            }
        }
        for(i=1;i<=m;i++){
            for(j=1;j<=f;j++){
                if(pd(i,j))
                mmap[i][m+j]=1;
            }
        }
        int ans=0;
        for(i=1;i<=m;i++){
            memset(vis,0,sizeof(vis));
            ans+=dfs(i);
        }
        printf("%d\n",n-ans);
    }
}