UVALive

題目大意：給出N個人的投票，每個人投票形式為以下兩種的其中一種
1.喜歡的狗的編號，討厭的貓的編號
2.喜歡的貓的編號，討厭的狗的編號
問如何選擇貓狗，才能滿足最多的人的投票

解題思路：找出每個喜歡貓的人和喜歡狗的人，然後分成兩個點集
如果喜歡的貓和對方討厭的貓相同，或者討厭的狗和對方喜歡的狗相同，那麼就表示這兩個人的願望是無法同時滿足的了，那麼連線
接下來，最大獨立集就是那些人的願望都能滿足的了

#include 
#include 
#include 
using namespace std;

#define N 510

struct voter{
    char a[5], b[5];
}cat[N], dog[N];

int c, d, v,  cat_cnt, dog_cnt;
int link[N];
char love[5], hate[5];
bool vis[N];
vector G[N];
void init() {
    scanf(%d%d%d, &c, &d, &v);
    cat_cnt = dog_cnt = 0;
    for (int i = 0; i < v; i++) {
        scanf(%s%s, love, hate);
        if (love[0] == 'C') {
            strcpy(cat[cat_cnt].a, love);
            strcpy(cat[cat_cnt].b, hate);
            G[cat_cnt++].clear();
        }
        else {
            strcpy(dog[dog_cnt].a, love);
            strcpy(dog[dog_cnt++].b, hate);
        }
    }

    for (int i = 0; i < cat_cnt; i++)
        for (int j = 0; j < dog_cnt; j++) 
            if (!strcmp(cat[i].a, dog[j].b) || !strcmp(cat[i].b, dog[j].a))
                G[i].push_back(j);
}

bool dfs(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            vis[v] = true;
            if (!(~link[v]) || dfs(link[v])) {
                link[v] = u;
                return true;
            }
        }
    }
    return false;
}

void solve() {
    int cnt = 0;
    memset(link, -1, sizeof(link));
    for (int i = 0; i < cat_cnt; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))
            cnt++;
    }
    printf(%d
, v - cnt);
}

int main() {
    int test;
    scanf(%d, &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}