题目地址：点击打开链接
题意：有p个孩子参观动物园，动物园里面有n只猫和m只狗，每个孩子喜欢猫讨厌狗，或者喜欢狗讨厌猫。只有把一个
孩子不喜欢的动物移走，喜欢的动物留下，这个孩子才会高兴。 问最多能使多少个孩子高兴。
思路: 一开始想着把猫和狗做二分图。。但不知道如何去建图了，而且高兴的孩子数也求不出。
正解应该是把喜欢猫的和喜欢狗的分为两个集合作二分图，如果A喜欢B讨厌的或者A讨厌B喜欢的那么建立关系。然后
求一个最大独立集（最大独立集=顶点数-最大匹配数）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn = 505; int n, m, p, numCater, numDoger, match[maxn]; bool vis[maxn]; vector<int> g[maxn]; struct node { char like[15], dislike[15]; }cater[maxn], doger[maxn]; bool dfs(int x) { for(int i = 0; i < g[x].size(); i++) { int to = g[x][i]; if(!vis[to]) { vis[to] = 1; if(match[to] == -1 || dfs(match[to])) { match[to] = x; return 1; } } } return 0; } int Hungary() { int res = 0; memset(match, -1, sizeof(match)); for(int i = 0; i < numCater; i++) { memset(vis, 0, sizeof(vis)); res += dfs(i); } return res; } int main(void) { while(cin >> n >> m >> p) { for(int i = 0; i <= p; i++) g[i].clear(); numCater = numDoger = 0; for(int i = 1; i <= p; i++) { char a[15], b[15]; scanf(" %s %s", a, b); if(a[0] == 'C') { strcpy(cater[numCater].like, a); strcpy(cater[numCater].dislike, b); numCater++; } else { strcpy(doger[numDoger].like, a); strcpy(doger[numDoger].dislike, b); numDoger++; } } for(int i = 0; i < numCater; i++) for(int j = 0; j < numDoger; j++) if(!strcmp(cater[i].like, doger[j].dislike) || ! strcmp(cater[i].dislike, doger[j].like)) g[i].push_back(j); printf("%d\n", p-Hungary()); } return 0; }
