HDOJ 2768问题中，如何求解Cat vs. Dog问题中的最大独立集？

本文共计654个文字，预计阅读时间需要3分钟。

题目：如何让猫咪和狗狗最满意（喜欢的有，不喜欢的没有）？

解题：通过电视节目《Cat vs Dog》了解每个参与者的喜好，安排猫咪和狗狗参与活动，让它们在喜欢的基础上进行互动，以获得更多观众满意。

题意:

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

题解:

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

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

Program:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<string.h>
#include<queue>
#define ll long long
#define esp 1e-5
#define MAXN 505
#define MAXM 50000000
#define oo 100000007
using 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;
}