题意：
给定n只猫，m条狗，p个人 给出每个人喜欢的一只动物和排斥的一只动物 （每个人喜欢一只狗排斥一只猫 || 喜欢一只猫排斥一只狗） 若动物园中有喜欢的动物且没有排斥的动物则此人算幸福 去掉一些动物使得最多的人幸福，问最多 多少人幸福。 思路： 问的是人数 则按人来建图 讨厌对方喜欢的动物则等价于这两个人互相排斥 把人分为喜欢狗和喜欢猫2类人，且喜欢猫的人不会排斥喜欢猫的人。 所以同类人之间不会互相排斥，则满足二部图。 问的是从中选最多的人使得彼此互不排斥，即最大du立集。 二分匹配求出最大匹配数 则结果为 最大 du 立集 = |X| + |Y| - 最大匹配数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
#define mod 1000000007
#define N 505
int lef[N], pn;//lef[v]表示Y集的点v 当前连接的点 , pn为x点集的点数
bool T[N]; //T[u] 表示Y集 u 是否已连接X集
vector<int>G[N]; //匹配边 G[X集].push_back(Y集) 注意G 初始化
bool match(int x){ // x和Y集 匹配 返回x点是否匹配成功
for(int i=0; i<G[x].size(); i++)
{
int v = G[x][i];
if(!T[v])
{
T[v] = true;
if(lef[v] == -1 || match( lef[v] )) //match(lef[v]) : 原本连接v的X集点 lef[v] 能不能和别人连，如果能 则v这个点就空出来和x连
{
lef[v] = x;
return true;
}
}
}
return false;
}
int solve(){
int ans = 0;
memset(lef, -1, sizeof(lef));
for(int i = 1; i<= pn; i++)//X集匹配，X集点标号从 1-pn 匹配边是G[左点].size()
{
memset(T, 0, sizeof(T));
if( match( i ) ) ans++;
}
return ans;
}
struct node{
int lik, dislik;
}a[505];
bool work(int x, int y){
if(a[x].dislik == a[y].lik)return true;
if(a[y].dislik == a[x].lik)return true;
return false;
}
int n, m, p;
int X[N], Y[N];
int main()
{
int i, j, k, u, v;
while(~scanf("%d %d %d",&n,&m,&p)){
for(i = 1; i<=p; i++)G[i].clear();
int xt = 1, yt = 1;
for(i = 1; i<=p; i++)
{
char c1=‘d‘,c2; while(c1!=‘D‘&&c1!=‘C‘)c1=getchar(); scanf("%d %c%d",&u,&c2,&v);
if(c1==‘C‘) v+=N; else u+=N;
a[i].lik = u; a[i].dislik = v;
if(c1==‘C‘)X[xt++] = i;
else Y[yt++] = i;
}
for(i = 1; i < xt; i++)
{
for(j = 1; j < yt; j++)
if(work(X[i],Y[j]))G[i].push_back(j);
}
pn = xt-1;
int ans = solve();
printf("%d\n",p-ans);
}
return 0;
}
HDU 3829 最大du立集=2个点集点数-最大匹配数,布布扣,bubuko.com
原文：http://blog.csdn.net/acmmmm/article/details/24267815