HDOJ 2768 - Cat vs. Dog 构图解二分图的最大独立集

HDOJ 2768 - Cat vs. Dog 构图解二分图的最大独立集

题意:

有一个电视节目叫"Cat vs Dog"..每个参与的嘉宾要么是喜欢某种狗讨厌某种猫,要么是喜欢某种猫讨厌某种狗..问怎样安排猫和狗使最多的嘉宾满意(其喜欢的有,不喜欢的没有)..

题解:

这道题更深入理解二分图的最大独立集..反过来做..将观众分为两部分..一部分喜欢猫,一部分喜欢狗..有边代表两个观众矛盾..求出其最大独立集(N-最大匹配)..得到的是没有边的最多点..根据构图的关系..这些点的个数就是答案...

这类问题可以总结为: 图是二分图,并且有些点对矛盾,找最多的点使得不矛盾...

Program:

#include#include#include#include#include#include#include#define ll long long#define esp 1e-5#define MAXN 505#define MAXM 50000000#define oo 100000007using namespace std; int n,match[MAXN],P[MAXN][2],color[MAXN];bool used[MAXN],g[MAXN][MAXN];bool dfs(int x){ for (int i=1;i<=n;i++) if (g[x][i] && !used[i]) { used[i]=true; if (!match[i] || dfs(match[i])) { match[i]=x; return true; } } return false;}int getmax(){ int sum=0; memset(match,0,sizeof(match)); for (int i=1;i<=n;i++) if (color[i]==1) { memset(used,false,sizeof(used)); sum+=dfs(i); } return sum;}int main() { int cases,C,D,i,x,y; char c; scanf("%d",&cases); while (cases--) { scanf("%d%d%d",&C,&D,&n); for (i=1;i<=n;i++) { do { c=getchar(); }while (c!='C' && c!='D'); scanf("%d",&x); if (c=='D') x+=C,color[i]=2; else color[i]=1; do { c=getchar(); }while (c!='C' && c!='D'); scanf("%d",&y); if (c=='D') y+=C; P[i][0]=x,P[i][1]=y; } memset(g,false,sizeof(g)); for (x=1;x<=n;x++) if (color[x]==1) for (y=1;y<=n;y++) if (P[x][0]==P[y][1] || P[y][0]==P[x][1]) g[x][y]=true; printf("%d\n",n-getmax()); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。