![HDU 3829 - Cat VS Dog (二分图最大独立集) HDU 3829 - Cat VS Dog (二分图最大独立集)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
题意:动物园有n只猫和m条狗,现在有p个小孩,他们有的喜欢猫,有的喜欢狗,其中喜欢猫的一定不喜欢狗,喜欢狗的一定不喜欢猫。现在管理员要从动物园中移除一些动物,如果一个小孩喜欢的动物留了下来而不喜欢的动物被移走,这个小孩会很高兴。现在问最多可以让多少个小孩高兴。
此题是求二分图最大独立集。
二分图比较明显,但是难在建图。这个题是找到最多的喜欢猫和喜欢狗而不互相冲突的小孩,这样我们将喜欢动物相互冲突的小孩之间连边,问题就变成了求二分图的最大独立集。
在二分图中,最大独立集=顶点数-最大匹配数。
求解二分图最大匹配可以用匈牙利算法。
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<cstdio> #include<vector> using namespace std; vector< pair<string,string> > vec1,vec2; ][]; ]; ]; bool match(int x) { ;i<vec2.size();++i) { if(gl[x][i]&&!vis[i]) { vis[i]=true; ||match(link[i])) { link[i]=x; return true; } } } return false; } int main() { int n,m,p; while(cin>>n>>m>>p) { string a,b; vec1.clear(); vec2.clear(); ; i<p; ++i) { cin>>a>>b; ]=='C') vec1.push_back(pair<string,string>(a,b)); else vec2.push_back(pair<string,string>(a,b)); } memset(gl,,sizeof(gl)); ; i<vec1.size(); ++i) { ; j<vec2.size(); ++j) if(vec1[i].first==vec2[j].second||vec1[i].second==vec2[j].first) gl[i][j]=true; } ; memset(link,-,sizeof(link)); ;i<vec1.size();++i) { memset(vis,,sizeof(vis)); if(match(i)) res++; } cout<<p-res<<endl; } ; }