学步园

/*************************************************************
题意：
给你n只猫，m只狗，p个人；
每个人都有一只喜欢的和一只讨厌的动物；
如果去掉某人讨厌的并且留下他喜欢的，
则这人是高兴的，让你求出最多高兴人数。
算法：
利用二分匹配求最大独立集
最大独立集=节点数-最大匹配数
建图：
喜欢猫的人左边，喜欢狗的人右边
二分图初始化为0；
只要有冲突的，权值为1。
****************************************************************/
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 555;
const int M = 5;
struct darling
{
    char like[M], dislike[M];
};
int map[N][N];
darling cat[N], dog[N];
int visit[N];
int match[N];
int n,m,p;
int k1,k2;//统计喜欢猫狗的数量
int find (int x)
{
    for (int i = 0; i < k2; i++)
        if (map[x][i] && !visit[i])
        {
            visit[i] = true;
            if (match[i] == -1 || find(match[i]))
            {
                match[i] = x;
                return 1;
            }
        }
    return 0;
}

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
    char like[M],dislike[M];
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d", &n, &m, &p);
        k1 = k2 = 0;
        for (int i = 0; i < p; i++)
        {
            scanf("%s%s", like, dislike);
            if (like[0] == 'C')
            {
                strcpy(cat[k1].like, like);
                strcpy(cat[k1].dislike, dislike);
                k1++;
            }
            else
            {
                strcpy(dog[k2].like, like);
                strcpy(dog[k2].dislike, dislike);
                k2++;
            }
        }

        memset(map, 0, sizeof(map));
        for (int i = 0; i < k1; i++)
            for (int j = 0; j < k2; j++)
                if (strcmp(cat[i].like, dog[j].dislike) == 0 || strcmp(cat[i].dislike, dog[j].like) == 0)
                    map[i][j] = 1;

        int res = 0;
        memset(match, -1, sizeof(match));
        for (int i = 0; i < k1; i++)
        {
            memset(visit, false, sizeof(visit));
            if (find(i))
                res++;
        }

        printf("%d\n", p-res);
    }
    return 0;
}