HDU 2768 Cat vs Dog(最大独立集)
/*题意：喜欢或者讨厌同一只猫和狗的人不能同时留下题解：将观众分成两组，左边是喜欢猫的，右边是喜欢狗的，如果存在冲突，则在这两个观众之间加一条边，于是问题转换成求最大独立集问题。*/#include <iostream>using namespace std;const int nMax = 505;struct Node{char str1[10];char str2[10];}cat[nMax], dog[nMax];int cat_num, dog_num;int map[nMax][nMax];int useif[nMax];int link[nMax];int c, d, v;int can(int t){for(int i = 0; i < dog_num; ++ i){if(!useif[i] && map[t][i]){useif[i] = 1;if(link[i] == -1 || can(link[i])){link[i] = t;return 1;}}}return 0;}int main(){//freopen("f://data.in", "r", stdin);int T;scanf("%d", &T);while(T --){memset(map, 0, sizeof(map));cat_num = dog_num = 0;scanf("%d %d %d", &c, &d, &v);for(int i = 0; i < v; ++ i){char a[10], b[10];scanf("%s %s", a, b);if(a[0] == 'C'){strcmp(cat[cat_num].str1, a);strcmp(cat[cat_num].str2, b);cat_num ++;}else{strcmp(dog[dog_num].str1, a);strcmp(dog[dog_num].str2, b);dog_num ++;}}for(int i = 0; i < cat_num; ++ i)for(int j = 0; j < dog_num; ++ j)if(!strcmp(cat[i].str1, dog[j].str2) || !strcmp(cat[i].str2, dog[j].str1))map[i][j] = 1;int ans = 0;memset(link, -1, sizeof(link));for(int i = 0; i < cat_num; ++ i){memset(useif, 0, sizeof(useif));if(can(i)) ans++;}printf("%d\n",v - ans);}return 0;}