HDU - 3829 Cat VS Dog(最大独立集-二分图最大匹配)

题目链接：点击查看

题目大意：给出n只狗和m只猫，现在有p个小朋友，每个小朋友都有一只喜欢的猫和一只不喜欢的狗，或者有一只喜欢的狗和一只不喜欢的猫，如果一个小朋友喜欢的动物还在，不喜欢的动物走了，那么这个小朋友是开心的，现在怎么样让小动物走，才能让开心的小朋友最多

题目分析：其实题目中的猫和狗都是没有的无效信息，意在让我们按照猫和狗划分二分图，其实不然，有多少种动物都没有关系，实际上只是和每个小朋友喜欢以及不喜欢的动物有关系

因为这个题目中，留下一个动物或赶走一个动物，会造成的影响是对于小朋友而言的，所以我们要对于小朋友划分二分图，具体怎么划分呢，因为题目明确说明了要求出开心的小朋友的最大集合，那么在这个集合中的小朋友必须满足的条件就是任意一个小朋友喜欢的动物和其他所有小朋友不喜欢的动物不能相同，同理任意一个小朋友不喜欢的动物也不能和其他小朋友喜欢的动物相同，这样一来只需要将集合中所有小朋友不喜欢的动物赶走就能让这些小朋友开心了

说到这里，这不就是要求集合中的所有点都互相独立，换句话说不就是要求最大独立集，所以我们让所有有矛盾的小朋友互相建边，用匈牙利跑一下最大独立集就是这个题目的答案了，因为我们建立的是无向边，所以最后匹配后的答案记得除以二

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=510;struct Node {string like,dislike; }a[N];int match[N],vis[N],vis_cnt,n,m,p;bool maze[N][N];bool dfs(int x) {for(int i=1;i<=p;i++){if(vis[i]!=vis_cnt&&maze[x][i]){vis[i]=vis_cnt;if(!match[i]||dfs(match[i])){match[i]=x;return true;}} }return false; }void init() {vis_cnt=0;memset(maze,false,sizeof(maze));memset(vis,-1,sizeof(vis));memset(match,0,sizeof(match)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d%d",&n,&m,&p)!=EOF){init();for(int i=1;i<=p;i++)cin>>a[i].like>>a[i].dislike;for(int i=1;i<=p;i++)for(int j=1;j<=p;j++)if(a[i].like==a[j].dislike||a[i].dislike==a[j].like)maze[i][j]=true;int ans=0;for(int i=1;i<=p;i++,vis_cnt++)if(dfs(i))ans++;printf("%d\n",p-ans/2);}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU - 3829 Cat VS Dog(最大独立集-二分图最大匹配)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。