题意：人和人之间如果满足4个条件的任意一条就不会成为夫妻，给定一些人，问从中最多能选多少人且保证任意两人不可能成为夫妻。

分析：由于条件之一是性别相同则不能成为夫妻。我们根据性别把人划分为两个集合，每个人是一个结点构成二分图，若两个人可能成为夫妻则连一条边。（同性之间不能成为夫妻，所以同集合内无边，此图必定为二分图）。题目要求是选出最多的人，且任意两人之间无边。这就是求二分图的最大独立集。只要用总人数－最大匹配数即可。

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; #define maxn 505 #define maxl 106 struct Person {
     int h; char music[maxl]; char sport[maxl]; } male[maxn], female[maxn]; int uN, vN, n; bool g[maxn][maxn]; int xM[maxn], yM[maxn]; bool chk[maxn]; bool SearchPath(int u) {
     int v; for (v = 0; v < vN; v++) if (g[u][v] && !chk[v])         {
                 chk[v] = true; if (yM[v] == -1 || SearchPath(yM[v]))             {
                     yM[v] = u;                 xM[u] = v; return true;             }         } return false; } int MaxMatch() {
     int u, ret = 0;     memset(xM, -1, sizeof(xM));     memset(yM, -1, sizeof(yM)); for (u = 0; u < uN; u++) if (xM[u] == -1)         {
                 memset(chk, false, sizeof(chk)); if (SearchPath(u))                 ret++;         } return ret; } void input() {
         scanf("%d", &n);     uN = vN = 0; for (int i = 0; i < n; i++)     {
     int a; char sex[3];         scanf("%d%s", &a, sex); if (sex[0] == 'M')         {
                 male[uN].h = a;             scanf("%s%s", male[uN].music, male[uN].sport);             uN++;         } else         {
                 female[vN].h = a;             scanf("%s%s", female[vN].music, female[vN].sport);             vN++;         }     } } bool couple(int a, int b) {
     if (abs(male[a].h - female[b].h) > 40) return false; if (strcmp(male[a].music, female[b].music)) return false; if (strcmp(male[a].sport, female[b].sport) == 0) return false; return true; } void make() {
         memset(g, 0, sizeof(g)); for (int i = 0; i < uN; i++) for (int j = 0; j < vN; j++) if (couple(i, j))                 g[i][j] = true; } int main() {
     //freopen("t.txt", "r", stdin);     int t;     scanf("%d", &t); while (t--)     {
             input();         make();         printf("%d\n", n - MaxMatch());     } return 0; }