BZOJ - 2744 朋友圈 （二分图上的最大团）

【题目大意】

在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。
两个国家看成是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 <bits/stdc++.h>

#define FOPI freopen("in.txt", "r", stdin);

#define FOPO freopen("out.txt", "w", stdout);

using namespace std;

typedef long long LL;

const int maxn =  + ;

int x, y;

int lnk[maxn], vis[maxn], del[maxn];

int a[maxn], b[maxn];

vector<int> v[maxn], odd, even;

vector<int> 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) %  == ) return true;

    int cnt = , tmp = x | y;

    while(tmp)

    {

        cnt += tmp % ;

        tmp >>= ;

    }

    return cnt % ;

}

bool dfs(int k)

{

    int sz = v[k].size();

    for (int i = ; i < sz; i++)

    {

        if (!vis[v[k][i]] && del[v[k][i]])

        {

            vis[v[k][i]] = ;

            if (lnk[v[k][i]] == - || dfs(lnk[v[k][i]]))

            {

                lnk[v[k][i]] = k;

                return true;

            }

        }

    }

    return false;

}

int hungary(int s = , int t = , int sum = )

{

    int cnt = ;

    memset(del, , sizeof(del));

    if (s) for (int i = ; i < frd[s].size(); i++) del[frd[s][i]]++;

    if (t) for (int i = ; i < frd[t].size(); i++) del[frd[t][i]]++;

    for (int i = ; i <= B; i++) cnt += del[i] = del[i] == sum;

    for (int i = ; i <= B; i++) v[i].clear();

    for (int i = ; i <= B; i++)

    for (int j = i+; j <= B; j++)

        if (del[i] && del[j] && !check(b[i], b[j])) build(i, j);

    int res = ;

    memset(lnk, -, sizeof(lnk));

    for (int i = ; i <= B; i++)

    {

        memset(vis, , sizeof(vis));

        if (del[i] && dfs(i)) res++;

    }

    return cnt - res / ;

}

int main()

{

    //FOPI;

    scanf("%d%d%d", &A, &B, &m);

    for (int i = ; i <= A; i++)

    {

        scanf("%d", &a[i]);

        if (a[i] % ) odd.push_back(i); else even.push_back(i);

    }

    for (int i = ; i <= B; i++) scanf("%d", &b[i]);

    for (int i = ; i <= m; i++)

    {

        scanf("%d%d", &x, &y);

        frd[x].push_back(y);

    }

    int ans = hungary();

    for (int i = ; i < odd.size(); i++) ans = max(ans, hungary(odd[i], , ) + );

    for (int i = ; i < even.size(); i++) ans = max(ans, hungary(even[i], , ) + );

    for (int i = ; i < odd.size(); i++)

        for (int j = ; j < even.size(); j++)

            ans = max(ans, hungary(odd[i], even[j], ) + );

    printf("%d\n", ans);

}

BZOJ - 2744 朋友圈 （二分图上的最大团）的相关教程结束。