传送
题面：有(n)个学生，每个学生有4个属性：身高，性别，最喜欢的音乐，最喜欢的体育比赛。选择尽量多的学生，满足下面4条中的至少一条：
（1）身高相差至少40厘米（不包含40）。
（2）性别相同。
（3）最喜欢的音乐属于不同类型。
（4）最喜欢的体育比赛相同。
这题也是一道二分图的典型例题，得做一遍才能形成这个思想。
首先我么按性别将所有点分成左右两部分。接下来如果左右两点间剩下三个条件都不满足，就连一条边。
那么我们要求的就是选尽量多的点，使选择的任意两个点之间没有边，即二分图的最大独立集。
最大独立集=总点数-最大匹配数。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 505;
const int maxe = 3e5 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n;
struct Stu
{
int h; string sex, mus, spo;
};
vector<Stu> M, F;
In bool check(Stu& a, Stu& b)
{
return abs(a.h - b.h) <= 40 && a.mus == b.mus && a.spo != b.spo;
}
struct Edge
{
int nxt, to;
}e[maxe];
int head[maxn], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
bool vis[maxn];
int lft[maxn];
In bool dfs(int now)
{
forE(i, now, v) //去看宏定义，改了一点！
if(!vis[v])
{
vis[v] = 1;
if(lft[v] == -1 || dfs(lft[v])) {lft[v] = now; return 1;}
}
return 0;
}
In int hung()
{
int ret = 0; Mem(lft, -1);
for(int i = 0; i < (int)M.size(); ++i)
{
Mem(vis, 0);
if(dfs(i + 1)) ++ret;
}
return ret;
}
In void init()
{
M.clear(), F.clear();
Mem(head, -1), ecnt = -1;
}
int main()
{
int T = read();
while(T--)
{
init();
n = read(); Stu tp;
for(int i = 1; i <= n; ++i)
{
tp.h = read();
cin >> tp.sex >> tp.mus >> tp.spo;
tp.sex[0] == 'M' ? M.push_back(tp) : F.push_back(tp);
}
for(int i = 0; i < (int)M.size(); ++i)
for(int j = 0; j < (int)F.size(); ++j)
if(check(M[i], F[j])) addEdge(i + 1, j + 1);
write(n - hung()), enter;
}
return 0;
}