匈牙利算法模板 2019牛客第五场多校F

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 5010

#define DEBUG 0

struct GRAPH  {
    vector<vector<int> > s;

    void ClearEdges() {
        for (auto& i : s)
            i.resize(0);
    }
    void Init(int n) {
        s.resize(n+1);
        ClearEdges();
    }
    void AddUndi(int u, int v) {
        s[u].push_back(v);
        s[v].push_back(u);
    }
};

int lowbit(int x) {
    return x & -x;
}
bool Judge(int x, int y) {
    x ^= y;
    x ^= lowbit(x);
    return x != 0;
}

bool left[MAXN], vis[MAXN];
int match[MAXN];
//If succeed return 1,else return 0
bool dfs_hungary(const GRAPH& g, int u) {
    for (int v : g.s[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (!match[v] || dfs_hungary(g, match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary(const GRAPH& g) {
    int ans = 0, n = g.s.size();
    memset(match, 0, n * sizeof(int));
    for (int i = 1; i < n; ++i) {
        if (left[i]) {
            memset(vis, 0, n * sizeof(vis[0]));
            if (dfs_hungary(g, i)) ++ans;
        }
    }
    return ans;
}

void dfs_color(const GRAPH& g, int u, bool c) {
    left[u] = c;
    vis[u] = true;
    for (int v : g.s[u])
        if (!vis[v])
            dfs_color(g, v, !c);
}
int Solve(const GRAPH& g) {
    memset(vis, 0, g.s.size() * sizeof(vis[0]));
    for (int i = 1; i < (int)g.s.size(); ++i)
        if (!vis[i])
            dfs_color(g, i, false);
    return hungary(g);
}

void dfs_independent(int ans[], int& len, const GRAPH& g, int u) {
	if (vis[u]) return;
	vis[u] = true;
	for (int v : g.s[u]) {
		if (!vis[v]) {
			vis[v] = true;
			dfs_independent(ans, len, g, match[v]);
		}
	}
}
//O(n+m)
void Independent(int ans[], int& len, const GRAPH& g) {
    Solve(g);
    static bool paired[MAXN];
    int n = g.s.size();
    memset(vis, 0, n * sizeof(vis[0]));
    memset(paired, 0, n * sizeof(paired[0]));
    for (int i = 1; i < n; ++i)       //start from 1
        if (match[i])
            paired[match[i]] = true;
    for (int i = 1; i < n; ++i)
        if (left[i] && !paired[i])
            dfs_independent(ans, len, g, i);
    for (int i = 1; i < n; ++i)
        if ((!vis[i] && !left[i]) || (vis[i] && left[i]))
            ans[len++] = i;
}
int main() {
    static int a[MAXN];
    GRAPH g;

    int n;
    scanf("%d", &n);
    g.Init(n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a+i);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (!Judge(a[i], a[j])) {
                g.AddUndi(i, j);
            }
        }
    }
    static int ans[MAXN];
    int len = 0;
    Independent(ans, len, g);

    printf("%d\n", len);
    for (int i = 0; i < len; ++i) {
        printf("%d", a[ans[i]]);
        if (i < len-1) {
            putchar(' ');
        }
    }

    return 0;
}