「Bzoj 2744」「HEOI2012」朋友圈 (二分图最大团)

Bzoj 2744
题意：见上。

本题本质上是求一个最大团。
分析A发现一个最大团中A最多有两个，否则是不合题意的
然后我们就可以枚举A有几个，然后将这几个A相连的B一起做一个最大团
我们发现B条件即为一个奇偶的二分图，在二分图上求最大团即可
然后这里最大团=总点数-补图最大独立集
要将奇数放在二分图左边，注意不清空数组的技巧

知识点
1、|不要打成||

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int T;

namespace flyinthesky {

    const int MAXN = 3005;

    int na, nb, m, a[205], b[MAXN], ma[205][MAXN];
    vector<int > G[MAXN];

    void ins(int u, int v) {G[u].push_back(v);}
    int chk(int x) {int ret = 0; while (x) ++ret, x &= (x - 1); return ret & 1;}

    int lk[MAXN], tm[MAXN], vis[MAXN], ban[MAXN], Tban, Tvis;

    bool hungary(int u) {
        if (ban[u] == Tban) return false;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (ban[v] != Tban && vis[v] != Tvis) {
                vis[v] = Tvis;
                if (tm[v] != Tban || !lk[v] || hungary(lk[v])) {
                    tm[v] = Tban, lk[v] = u;
                    return true;
                } 
            }
        }
        return false;
    }

    int work(int x = 0, int y = 0) {
        int ret = 0;
        ++Tban;
        for (int i = 1; i <= nb; ++i) if (ma[x][i] || ma[y][i]) ban[i] = Tban, ++ret;
        for (int i = 1; i <= nb; ++i) if ((b[i] & 1) == 1) ++Tvis, ret += hungary(i); //
        return nb - ret;
    }

    void clean() {
        ms(lk, 0), ms(tm, 0), ms(vis, 0), ms(ban, 0), Tban = Tvis = 0;
        for (int i = 0; i <= 201; ++i)
        for (int j = 0; j <= 3001; ++j) ma[i][j] = 1;
    }
    int solve() {

        cin >> na >> nb >> m;
        clean();
        for (int i = 1; i <= na; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= nb; ++i) scanf("%d", &b[i]);
        for (int x, y, i = 1; i <= m; ++i) scanf("%d%d", &x, &y), ma[x][y] = 0;
        for (int i = 1; i <= nb; ++i) ma[0][i] = 0;

        for (int x = 1; x <= nb; ++x) if ((b[x] & 1) == 1) {
            for (int y = 1; y <= nb; ++y) if ((b[y] & 1) == 0) {
                if (chk(b[x] | b[y]) == 0) ins(x, y); // |
            }
        }

        int ans = work();
        for (int i = 1; i <= na; ++i) ans = max(ans, work(i) + 1);
        for (int u = 1; u <= na; ++u) if ((a[u] & 1) == 1)
        for (int v = 1; v <= na; ++v) if ((a[v] & 1) == 0) ans = max(ans, work(u, v) + 2);

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

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}