这个题,因为只有两个集合,很容易让人想到二分图最大匹配
所以我们把喜欢猫和喜欢狗的人分为两个集合。
然后如果A君喜欢B君讨厌的,或者A君讨厌B君喜欢的
那么就把A君和B君之间连一条边。
然后再求一个最大独立集,就是答案了。
我的代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
char like[5];
char dislike[5];
};
node cater[505],doger[505];
int n,m,p;
int num1,num2;
int used[505];
bool map[505][505];
int link[505];......
阅读全文