题目链接：https://vjudge.net/problem/HDU-3829
题目大意：
有\(P\)个小孩，\(N\)只猫，\(M\)只狗。每个小孩都有自己喜欢的某一只宠物和讨厌的某一只宠物（其中必定一只是猫，一只是狗），如果某个小孩喜欢的宠物被留下，而讨厌的宠物被带走，则这个小孩就会很开心。问要留下哪些宠物才能使得开心的小孩最多，求出这个最多的数量。
知识点： 最大独立集
解题思路：
对于两个小孩，如果其中一个喜欢的宠物刚好是另一个讨厌的宠物，那么这两个小孩不能一起开心。将不能一起开心的小孩匹配起来，则最多的开心小孩的数目即为该二分图的最大独立集。
AC代码：
#include <bits/stdc++.h> using namespace std; bool line[][],used[];
int to[];
struct per{
int like,dislike;
}chi[];
int turn(char s[]){
int len=strlen(s);
int ret=;
for(int i=;i<len;i++){
ret*=;
ret+=s[i]-'';
}
if(s[]=='C') ret+=;
return ret;
}
bool check(int x,int n){
for(int j=;j<=n;j++){
if(line[x][j]&&!used[j]){
used[j]=true;
if(to[j]==||check(to[j],n)){
to[j]=x;
return true;
}
}
}
return false;
}
int main(){
int N,M,P;
char i1[],i2[];
while(scanf("%d%d%d",&N,&M,&P)==){
for(int i=;i<=P;i++){
for(int j=;j<=P;j++) line[i][j]=false;
to[i]=;
}
for(int i=;i<=P;i++){
scanf("%s %s",i1,i2);
chi[i].like=turn(i1);
chi[i].dislike=turn(i2);
} for(int i=;i<=P;i++){
for(int j=i+;j<=P;j++){
if(chi[i].like==chi[j].dislike||chi[i].dislike==chi[j].like){
line[i][j]=line[j][i]=true;
}
}
}
int all=;
for(int i=;i<=P;i++){
memset(used,false,sizeof(used));
if(check(i,P)) all++;
}
printf("%d\n",(*P-all)/);
}
return ;
}