题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3829
题目大意：
给定N个猫，M个狗，P个小朋友，每个小朋友都有喜欢或者不喜欢的某猫或者某狗
管理员从中删除一些猫狗，使得尽可能多的小朋友开心
思路：
假设A小朋友喜欢的猫是B小朋友所不喜欢的，或者说A不喜欢的狗是B喜欢的，那么说明两者之间存在矛盾关系
问题就是求出互相之间没有矛盾的小朋友的集合
那么就是点数-最大匹配数的问题了，就是读入数据有点麻烦
代码：
1 #include <iostream> 2 #include <string> 3 #include <map> 4 #include <stdio.h> 5 #include <string.h> 6 using namespace std; 7 const int maxn=505; 8 int N,M,P,c_cnt,d_cnt; 9 int g[maxn][maxn],vis[maxn],who[maxn]; 10 struct node { 11 int data[2][205];//[0][]like [1][]don't like 12 } ans[maxn]; 13 map<string,int> c,d; 14 map<string,int>::iterator it; 15 string s; 16 void rs(int i,int dir) { 17 if(s[0]=='C') { 18 if(!c.count(s)) c.insert(pair<string,int>(s,c_cnt++)); 19 it=c.find(s); 20 ans[i].data[dir][it->second]=1; 21 } else { 22 if(!d.count(s)) d.insert(pair<string,int>(s,d_cnt++)); 23 it=d.find(s); 24 ans[i].data[dir][it->second]=1; 25 } 26 } 27 void read() { 28 memset(g,0,sizeof(g)); 29 memset(who,0,sizeof(who)); 30 memset(ans,0,sizeof(ans)); 31 c.clear(); 32 d.clear(); 33 c_cnt=1; 34 d_cnt=101; 35 for(int i=1; i<=P; ++i) { 36 cin>>s;//like 37 int dir=0; 38 rs(i,dir); 39 cin>>s;//don't like 40 dir^=1; 41 rs(i,dir); 42 } 43 for(int i=1; i<=P; ++i) 44 for(int j=i+1; j<=P; ++j) 45 for(int k=1; k<=200; ++k) 46 if((ans[i].data[0][k]==1&&ans[j].data[1][k]==1)||(ans[i].data[1][k]==1&&ans[j].data[0][k]==1)) 47 g[i][j]=g[j][i]=1; 48 } 49 bool Find(int x) { 50 for(int i=1; i<=P; ++i) { 51 if(g[x][i]&&!vis[i]) { 52 vis[i]=1; 53 if(!who[i]||Find(who[i])) { 54 who[i]=x; 55 return true; 56 } 57 } 58 } 59 return false; 60 } 61 void slove() { 62 int sum=0; 63 for(int i=1; i<=P; ++i) { 64 memset(vis,0,sizeof(vis)); 65 if(Find(i)) sum++; 66 } 67 cout<<P-sum/2<<endl; 68 } 69 int main() { 70 while(cin>>N>>M>>P) { 71 read(); 72 slove(); 73 } 74 return 0; 75 }