UVA

UVA

题意：

给你 n 个人的 性别 身高， 喜欢的运动和音乐。 告诉你一些两个人能在一起的条件， 问 最多多少人 在一起？

思路：

有性别之分。

可以建成一个二分图。

然后反向建边， 如果男i 和 女j 不能再一起 就连一条边。

然后这样， 二分图的最大独立集 就是 答案。 所有人都不连边， 所有人都可以在一起。

总数 - 最大匹配数 即是答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;const int maxn = 500 + 7;
struct Node{int h;char sex[3];char music[102];char sport[102];
}p[maxn];
vector<int>g[maxn];int aaa(int x){if (x < 0) return -x;return x;
}
bool check(int i,int j){if (p[i].sex[0] == p[j].sex[0]) return true;if (aaa(p[i].h - p[j].h) > 40) return true;if (strcmp(p[i].music, p[j].music)) return true;if (!strcmp(p[i].sport, p[j].sport)) return true;return false;
}int vis[maxn];int match[maxn];bool hungry(int x){for (int i = 0; i < g[x].size(); ++i){int v = g[x][i];if (vis[v]) continue;vis[v] = 1;if (match[v] == -1 || hungry(match[v])){match[v] = x;return true;}}return false;
}int solve(int n){int ans = 0;memset(match,-1,sizeof match);for (int i = 0; i < n; ++i){memset(vis,0,sizeof vis);if (hungry(i))++ans;}return ans;
}
int main(){int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for (int i = 0; i < n; ++i){g[i].clear();scanf("%d%s%s%s", &p[i].h, p[i].sex, p[i].music, p[i].sport);}for (int i = 0; i < n; ++i){if (p[i].sex[0] == 'M') continue;for (int j = 0; j < n; ++j){if (i == j) continue;if (!check(i, j)) g[i].push_back(j);}}int ans = solve(n);printf("%d\n", n - ans);}return 0;
}