2019牛客暑期多校训练营(第五场) maximum clique 1

题意：给出n个不相同的数，问选出尽量多的数且任两个数字二进制下不同位数大于等于2。

解法：能想到大于等于2反向思考的话，不难发现这是一个二分图，那么根据原图的最大团等于补图的最大独立点集，此问题就变成 任两个二进制位数相差等于1之间连边（这就是补图），然后求这个图的最大独立点集，仔细观察发现补图是个二分图。那么就可以得到最大独立点集=n-最大匹配。

那么怎么构造一个可行方案呢？参考《算法竞赛进阶指南》的办法，1求出最大匹配  2从左边非匹配点出发跑增广路同时把路上的点标记 3最后左边非匹配点和右边匹配点组成最小点覆盖。    那么最大独立点集就是除了最小点覆盖的点啦。

以前没写过构造最大独立点集，这题写了记录下来以免以后忘了。

#include<bits/stdc++.h>

using namespace std;

const int N=5e3+;

typedef long long LL;

int n,col[N],match[N],a[N];

map<LL,int> mp;

vector<int> G[N];

void dfs1(int x,int c) {

    col[x]=c;

    for (int i=;i<G[x].size();i++) {

        int y=G[x][i];

        if (!col[y]) dfs1(y,-col[x]);

    }

}

bool vis[N],Ans[N];

bool dfs(int x) {

    vis[x]=;

    for (int i=;i<G[x].size();i++) {

        int y=G[x][i];

        if (!vis[y]) {

            vis[y]=;

            if (!match[y] || dfs(match[y])) {

                match[y]=x; match[x]=y;

                return ;

            }

        }

    }

    return ;

}

int main()

{

    scanf("%d",&n);

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

    for (int i=;i<=;i++) mp[1LL<<i]=;

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

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

            if (mp.count(a[i]^a[j])) G[i].push_back(j),G[j].push_back(i);

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

        if (!col[i]) dfs1(i,);

    int ans=;

    for (int i=;i<=n;i++) {

        if (col[i]==) continue;

        memset(vis,,sizeof(vis));

        if (dfs(i)) ans++;

    }

    cout<<n-ans<<endl;

    memset(vis,,sizeof(vis));

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

        if (col[i]== && !match[i]) dfs(i);

    memset(Ans,,sizeof(Ans));

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

        if (col[i]== && !vis[i] || col[i]== && vis[i]) Ans[i]=;

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

        if (!Ans[i]) printf("%d ",a[i]);

    return ;

}