Description
Input
Output
Sample Input
Sample Output
Hint
Case 2: Remove D1 and D2, that makes child 1, 2, 3 happy.
题目大意：院子里有m条狗，n条猫。p个小孩。这p个小孩，每个小孩要么喜欢狗，讨厌猫；要么喜欢猫，讨厌狗。管理员要把一些狗或者猫驱赶走，如果某个小孩喜欢的动物没被赶走且不喜欢的动物被赶走，他就会高兴。问你最多能让多少小孩高兴。
解题思路：最大独立集：选择尽量多的结点，使得结点之间没有边。喜欢某条狗的小孩会跟不喜欢这条狗的小孩有矛盾，同样猫也一样。在有矛盾的小孩之间连一条边。然后求解最大独立集，即剩下的小孩都没有矛盾。由于不是选择的真正的X部，Y部，而是采用的拆点，连了双向边，所以最后最大匹配应该除以2。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1000;
const int INF = 0x3f3f3f3f;
vector<int>G[maxn];
int Mx[maxn], My[maxn], dx[maxn], dy[maxn], used[maxn], dis;
int Map[maxn][maxn];
bool SearchP(int _n){
queue<int>Q;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
int dis = INF;
for(int i = 1; i <= _n; i++){
if(Mx[i] == -1){
dx[i] = 0;
Q.push(i);
}
}
int v;
while(!Q.empty()){
int u = Q.front(); Q.pop();
if(dx[u] > dis) break;
for(int i = 0; i < G[u].size(); i++){
v = G[u][i];
if(dy[v] == -1){
dy[v] = dx[u] + 1;
if(My[v] == -1){
dis = dy[v];
}else{
dx[My[v]] = dy[v] + 1;
Q.push(My[v]);
}
}
}
}
return dis != INF;
}
int dfs(int u){
int v;
for(int i = 0; i < G[u].size(); i++){
v = G[u][i];
if(!used[v] && dy[v] == dx[u] + 1){
used[v] = 1;
if(My[v] != -1 && dy[v] == dis){
continue;
}
if(My[v] == -1 || dfs(My[v])){
Mx[u] = v;
My[v] = u;
return true;
}
}
}
return false;
}
int MaxMatch(int ln,int rn){
int ret = 0;
memset(Mx,-1,sizeof(Mx));
memset(My,-1,sizeof(My));
while(SearchP(ln)){
memset(used,0,sizeof(used));
for(int i = 1; i <= ln; i++){
if(Mx[i] == -1 && dfs(i)){
ret++;
}
}
}
return ret;
}
char like[maxn][20], dislike[maxn][20];
int main(){
int T, cas = 0, n, m, N, M, k, P;
while(scanf("%d%d%d",&N,&M,&P)!=EOF){
for(int i = 0; i <= P; i++){
G[i].clear();
}
for(int i = 1; i <= P; i++){
scanf("%s%s",like[i],dislike[i]);
}
for(int i = 1; i <= P; i++){
for(int j = i+1; j <= P; j++){
if(strcmp(like[i],dislike[j])== 0 || strcmp(dislike[i],like[j]) == 0){
G[i].push_back(j);
G[j].push_back(i);
}
}
}
n = m = P;
int res = MaxMatch(n,m);
printf("%d\n", n - res/2);
}
return 0;
}
HDU 3829——Cat VS Dog——————【最大独立集】
原文：http://www.cnblogs.com/chengsheng/p/4957426.html