题目链接:
思路:把喜欢cat的和喜欢dog的看成两个集合,如果这两个集合有冲突,即cat.love==dog.hate或者cat.hate==dog.love,这连边,代表有矛盾,那么最后的结果不就是求一下最大独立集吗。
最大独立集=顶点数-最大匹配。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define MAXN 2222 8 struct Node { 9 string love;10 string hate;11 } cat[MAXN],dog[MAXN];12 int cat_cnt,dog_cnt;13 bool map[MAXN][MAXN];14 bool mark[MAXN];15 int ly[MAXN];16 char s1[11],s2[11];17 18 int dfs(int u) {19 for(int v=0; v