http://acm.hdu.edu.cn/showproblem.php?pid=3829
hdu 3829 Cat VS Dog
题意：动物园有n只狗 m只猫，p个小朋友。规定一个小朋友喜欢猫就讨厌狗，喜欢狗就讨厌猫，要是他喜欢还留在动物园 不喜欢的搬出动物园 他就会很开心 求最多会有多少小朋友开心
【思路】：两个小朋友间 要是他喜欢的你不喜欢 或你喜欢的他不喜欢 说明你俩矛盾 就在你们两个这之间连一条边 求出整个图的最大独立集 也就是说这集合里的点两两之间没有矛盾的 可以一个一个被满足。
#include<iostream>#include<string.h>#include<vector> #include<stdio.h> using namespace std;vector<int > g[1002];int mark[1002],link[1002],n,m,p;struct node{char x[5];char y[5];}no[1002];int dfs(int x){for(int i=0;i<g[x].size ();i++){int v=g[x][i];if(!mark[v]){mark[v]=1;if(link[v]==-1||dfs(link[v])){link[v]=x;return 1;}}}return 0;}int main(){int i,j,t,a,b;char c1,c2;while(~scanf("%d%d%d",&n,&m,&p)){for(i=0;i<p;i++)g[i].clear ();for(i=0;i<p;i++){ //getchar();cin>>no[i].x>>no[i].y;}// printf("oo \n");for(i=0;i<p;i++)for(j=i+1;j<p;j++)if(i!=j&&(strcmp(no[i].x,no[j].y)==0||strcmp(no[i].y,no[j].x)==0)){g[i].push_back (j);g[j].push_back (i);}memset(link,-1,sizeof(link));int ans=0;for(i=0;i<p;i++){memset(mark,0,sizeof(mark));ans+=dfs(i);}// printf("a %d\n",ans);ans/=2;printf("%d\n",p-ans);}return 0;}