2015
04-13

Cat VS Dog

The zoo have N cats and M dogs, today there are P children visiting the zoo, each child has a like-animal and a dislike-animal, if the child’s like-animal is a cat, then his/hers dislike-animal must be a dog, and vice versa.
Now the zoo administrator is removing some animals, if one child’s like-animal is not removed and his/hers dislike-animal is removed, he/she will be happy. So the administrator wants to know which animals he should remove to make maximum number of happy children.

The input file contains multiple test cases, for each case, the first line contains three integers N <= 100, M <= 100 and P <= 500.
Next P lines, each line contains a child’s like-animal and dislike-animal, C for cat and D for dog. (See sample for details)

The input file contains multiple test cases, for each case, the first line contains three integers N <= 100, M <= 100 and P <= 500.
Next P lines, each line contains a child’s like-animal and dislike-animal, C for cat and D for dog. (See sample for details)

1 1 2
C1 D1
D1 C1

1 2 4
C1 D1
C1 D1
C1 D2
D2 C1

1
3

HintCase 2: Remove D1 and D2, that makes child 1, 2, 3 happy. 

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 510
#define N 250010
int match[M];
string like[M], dislike[M]; //喜欢，不喜欢
bool use[M];
int num;
int child;

void add(int u, int v) //邻接表存图
{
Key[num] = v;
}

bool find(int u) //匹配
{
int temp;
for(int i = Head[u]; i != -1; i = Next[i])
{
temp = Key[i];
if(!use[temp])
{
use[temp] = true;
if(match[temp] == -1 || find(match[temp]))
{
match[temp] = u;
return true;
}
}
}
return false;
}

int hungary() //匈牙利算法，拆点匹配
{
int sum = 0;
for(int i = 0; i < child; ++i)
{
memset(use, false, sizeof(use));
if(find(i))
sum++;
}
return sum;
}

int main()
{
int cat, dog;
string likeit, dislikeit;
while(scanf("%d%d%d", &cat, &dog, &child) != EOF)
{
num = 0;
memset(match, -1, sizeof(match));
for(int i = 0; i < child; ++i)
{
cin>>likeit>>dislikeit; //喜欢动物，不喜欢动物
like[i] = likeit; //记录
dislike[i] = dislikeit;
}
for(int i = 0; i < child; ++i) //必须建立双向边
for(int j = 0; j < child; ++j)
if(like[i].compare(dislike[j]) == 0 || dislike[i].compare(like[j]) == 0) //加入矛盾边
}