题意：
有一个老师想组织学生出去旅游，为了避免他们之间有情侣产生，他制定了一系列的条件，满足这些条件之一，那么这些人理论上就不会成为情侣：
身高相差40cm；性别相同；喜欢的音乐风格不同；最喜欢的运动相同。
给出若干个学生的身高，性别，喜欢的音乐风格和喜欢的运动，问最多有多少人可以出去。
思路：
对于两个人，如果以上所有条件都不满足，那么就在他们之间连边，说明他们不能同时去。
问题就转化成了求一个二分图的最大独立集。（独立集是两两之间不存在边的点的集合，最大顾名思义）
最大独立集 = 点数- 最小点覆盖 = 点数 – 最大匹配
匈牙利算法，复杂度O(n^3)。
代码：
#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
using namespace std; const int N = ; vector<int> g[N];
int link[N];
bool vis[N]; struct node
{
int hei;
string sex,music,sport; node(int a,string b,string c,string d)
{
hei = a;
sex = b;
music = c;
sport = d;
}
}; vector<node> ns; bool dfs(int u)
{
for (int i = ;i < g[u].size();i++)
{
int v = g[u][i]; if (!vis[v])
{
vis[v] = ; if (link[v] == - || dfs(link[v]))
{
link[v] = u;
link[u] = v; return true;
}
}
} return false;
}
int solve(int n)
{
int cnt = ; memset(link,-,sizeof(link)); for (int i = ;i < n;i++)
{
if (link[i] == -)
{
memset(vis,,sizeof(vis));
if (dfs(i)) cnt++;
}
} return cnt;
} int mabs(int x)
{
return x >= ? x : -x;
} int main()
{
int t; scanf("%d",&t); while (t--)
{
int n; scanf("%d",&n); ns.clear(); for (int i = ;i < n;i++)
{
g[i].clear();
int a;
string b,c,d; cin >> a >> b >> c >> d; ns.push_back(node(a,b,c,d));
} for (int i = ;i < n;i++)
{
for (int j = i + ;j < n;j++)
{
bool f = ; if (mabs(ns[i].hei - ns[j].hei) > ) f = ;
if (ns[i].sex == ns[j].sex) f = ;
if (ns[i].music != ns[j].music) f = ;
if (ns[i].sport == ns[j].sport) f = ; if (!f)
{
g[i].push_back(j);
g[j].push_back(i);
}
}
} int ans = solve(n); printf("%d\n",n - ans);
} return ;
}