【题目大意】

    在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。

两个国家看成是AB两国，现在是两个国家的描述：

    1.A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果a xor b mod 2=1，那么这两个人都是朋友，否则不是；

    2.B国：每个人都有一个友善值，当两个B国人的友善值a、b，如果a xor b mod 2=0或者 (a or b)化成二进制有奇数个1，那么两个人是朋友，否则不是朋友；

    3.A、B两国之间的人也有可能是朋友，数据中将会给出A、B之间“朋友”的情况。

    4.在AB两国，朋友圈的定义：一个朋友圈集合S，满足S∈A∪ B，对于所有的i，j∈ S，i和j是朋友。

    由于落后的古代，没有电脑这个也就成了每年最大的难题，而你能帮他们求出最大朋友圈的人数吗？

 

【题目解析】

A国人相互为朋友的只有可能是奇数和偶数。

所以S中A国人员可能：无、1奇数、1偶数、1奇数+1偶数。

 

B国人相互为朋友的可能是奇数和奇数、偶数和偶数、部份奇数和偶数。

所以B国人朋友关系的补图只有可能是奇数和偶数。是一个二分图。

补图的最大独立集就是是原图中的最大团。

二分图上的最大独立集 = 点数 - 最大匹配。

 

所以可以枚举上述情况，看选哪个A国人，然后把B国中的、被选择A国人的朋友中建补图，求最大匹配。

看众多大佬用时间戳代替memset。我不会。

 

#include 
     
      #define FOPI freopen("in.txt", "r", stdin);#define FOPO freopen("out.txt", "w", stdout);using namespace std;typedef long long LL;const int maxn = 3000 + 1000;int x, y;int lnk[maxn], vis[maxn], del[maxn];int a[maxn], b[maxn];vector
      
        v[maxn], odd, even;vector
       
         frd[maxn];int A, B, m;void build(int x, int y){    v[x].push_back(y), v[y].push_back(x);}bool check(int x, int y){    if ((x ^ y) % 2 == 0) return true;    int cnt = 0, tmp = x | y;    while(tmp)    {        cnt += tmp % 2;        tmp >>= 1;    }    return cnt % 2;}bool dfs(int k){    int sz = v[k].size();    for (int i = 0; i < sz; i++)    {        if (!vis[v[k][i]] && del[v[k][i]])        {            vis[v[k][i]] = 1;            if (lnk[v[k][i]] == -1 || dfs(lnk[v[k][i]]))            {                lnk[v[k][i]] = k;                return true;            }        }    }    return false;}int hungary(int s = 0, int t = 0, int sum = 0){    int cnt = 0;    memset(del, 0, sizeof(del));    if (s) for (int i = 0; i < frd[s].size(); i++) del[frd[s][i]]++;    if (t) for (int i = 0; i < frd[t].size(); i++) del[frd[t][i]]++;    for (int i = 1; i <= B; i++) cnt += del[i] = del[i] == sum;    for (int i = 1; i <= B; i++) v[i].clear();    for (int i = 1; i <= B; i++)    for (int j = i+1; j <= B; j++)        if (del[i] && del[j] && !check(b[i], b[j])) build(i, j);    int res = 0;    memset(lnk, -1, sizeof(lnk));    for (int i = 1; i <= B; i++)    {        memset(vis, 0, sizeof(vis));        if (del[i] && dfs(i)) res++;    }    return cnt - res / 2;}int main(){    //FOPI;    scanf("%d%d%d", &A, &B, &m);    for (int i = 1; i <= A; i++)    {        scanf("%d", &a[i]);        if (a[i] % 2) odd.push_back(i); else even.push_back(i);    }    for (int i = 1; i <= B; i++) scanf("%d", &b[i]);    for (int i = 1; i <= m; i++)    {        scanf("%d%d", &x, &y);        frd[x].push_back(y);    }    int ans = hungary();    for (int i = 0; i < odd.size(); i++) ans = max(ans, hungary(odd[i], 0, 1) + 1);    for (int i = 0; i < even.size(); i++) ans = max(ans, hungary(even[i], 0, 1) + 1);    for (int i = 0; i < odd.size(); i++)        for (int j = 0; j < even.size(); j++)            ans = max(ans, hungary(odd[i], even[j], 2) + 2);    printf("%d\n", ans);}