点击打开链接
大意:当一个人喜欢的留下来，而不喜欢的移走时，他会很高兴。
想法：喜欢猫的是一个集合，喜欢狗的是另一个集合。当其中一个人喜欢的，和另外一个人不喜欢的一样时，就可以形成一个匹配，求出最大匹配。
最大独立集=节点数-最大匹配。
#include"stdio.h"
#include"string.h"
#define N 501
struct node
{char hate[5],like[5];
}cat[N],dog[N];
int map[N][N],v[N],link[N];
int C,D,n,m,t;
int dfs(int k)
{int i;for(i=0;i<D;i++){if(map[k][i]&&!v[i]){v[i]=1;if(link[i]==-1||dfs(link[i])){link[i]=k;return 1;}}}return 0;
}
int main()
{int T,i,j,ans;char s[N],ss[N];scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&t);C=D=0;for(i=0;i<t;i++){scanf("%s %s",s,ss);if(s[0]=='C'){strcpy(cat[C].like,s);strcpy(cat[C].hate,ss);C++;}else{strcpy(dog[D].like,s);strcpy(dog[D].hate,ss);D++;}}memset(map,0,sizeof(map));for(i=0;i<C;i++){for(j=0;j<D;j++){if(strcmp(cat[i].hate,dog[j].like)==0||strcmp(cat[i].like,dog[j].hate)==0)map[i][j]=1;}}memset(link,-1,sizeof(link));ans=0;for(i=0;i<C;i++){memset(v,0,sizeof(v));if(dfs(i))ans++;}printf("%d\n",t-ans);}return 0;
}