<题目链接>
题目大意：
动物园有n条狗。m头猫。p个小孩，每一个小孩有一个喜欢的动物和讨厌的动物。如今动物园要转移一些动物。假设一个小孩喜欢的动物在，不喜欢的动物不在，他就会happy。问动物最多能使几个小孩happy。
解题分析：
因为本题不同的小孩之间喜好可能会产生冲突，所以，要使最多的小孩满意，不妨将这些冲突的小孩之间相互连线，然后求出不产生冲突的最大点集，于是本题就转化为了最大独立集问题。最大独立集=总点数-最大匹配数。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
using namespace std; const int M=;
int match[M];
bool vis[M];
vector<int>map[M];
string lk[M],dislk[M];
int n,m,p,uN;
bool dfs(int u){
for(int i=;i<map[u].size();i++){
if(!vis[map[u][i]]){
vis[map[u][i]]=true;
if(match[map[u][i]]==-||dfs(match[map[u][i]])){
match[map[u][i]]=u;
return true;
}
}
}
return false;
}
int hungary(){
int res=;
memset(match,-,sizeof(match));
for(int u=;u<p;u++){
memset(vis,false,sizeof(vis));
res+=dfs(u);
}
return res;
}
int main(){
while(scanf("%d%d%d",&n,&m,&p)!=EOF){
for(int i=;i<M;i++)map[i].clear();
for(int i=;i<p;i++){
cin>>lk[i]>>dislk[i];
}
for(int i=;i<p;i++)
for(int j=i+;j<p;j++)
if(lk[i]==dislk[j]||dislk[i]==lk[j]){ //产生矛盾的人之间建立无向边
map[i].push_back(j);
map[j].push_back(i);
}
printf("%d\n",p-hungary()/); //最大独立集=总点数-最大匹配
}
return ;
}
2018-11-16