题意：
p个人 每个人有喜欢和讨厌的动物 如果选出的动物中包含这个人喜欢的动物同时不包含他讨厌的动物那么这个人会开心 问 最多几个人开心
思路：
二分图最大独立集 利用人与人之间的冲突建边 求最大匹配即可
注意：
题中的样例给出动物的名字是D1、C1之类的 其实名字可能比这个长… 所以数组开长点
代码：
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef unsigned long long LL; #define N 510 struct edge { int v, next; } ed[N * N]; int vis[N], match[N], head[N]; int n, tot; char like[N][10], dislike[N][10]; void add(int u, int v) { ed[tot].v = v; ed[tot].next = head[u]; head[u] = tot++; } bool dfs(int u) { int i, v; for (i = head[u]; ~i; i = ed[i].next) { v = ed[i].v; if (!vis[v]) { vis[v] = 1; if (!match[v] || dfs(match[v])) { match[v] = u; return true; } } } return false; } int bimatch() { int i, sol = 0; memset(match, 0, sizeof(match)); for (i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); if (dfs(i)) sol++; } return sol; } int main() { int i, j, ans; while (~scanf("%d%d%d", &i, &j, &n)) { for (i = 1; i <= n; i++) scanf("%s%s", like[i], dislike[i]); memset(head, -1, sizeof(head)); tot = 0; for (i = 1; i <= n; i++) { for (j = i + 1; j <= n; j++) { if (!strcmp(like[i], dislike[j]) || !strcmp(like[j], dislike[i])) { add(i, j); add(j, i); } } } ans = n - bimatch() / 2; printf("%d\n", ans); } return 0; }