2019 牛客暑期多校训练营 第五场 F maximum clique 1 最大独立集

#include <iostream>
#include <cstring>
#include <queue>
#include <stdio.h>
using namespace std;
#define INF 0x7ffffff
const int M = 1000005;
struct E{
    int nxt,v,w;
};
E edge[M];
int dpth[M],head[M],cnt;
int n,m,s,t;
void add(int u,int v,int w){
    cnt++;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
    cnt++;
    edge[cnt].v = u;
    edge[cnt].w = 0;
    edge[cnt].nxt = head[v];
    head[v] = cnt;
}
//初始化从0开始存边 i^1是i的反向边
void init(){
    cnt=-1;
    memset(head,-1,sizeof(head));
}
//初始化分层图
bool bfs(){
    memset(dpth,0,sizeof(dpth));
    queue<int> q; q.push(s); dpth[s] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v,i=head[u];i!=-1;i=edge[i].nxt){
            {
                v = edge[i].v; 
                if(edge[i].w>0&&dpth[v]==0){
                    dpth[v] = dpth[u]+1;
                    q.push(v);
                }
            }
        }
    }
    if(dpth[t]!=0)
    return true;
    else return false;
}
int dfs(int u,int dist){
    if(u==t)
     return dist;
    for(int v,i=head[u];i!=-1;i=edge[i].nxt){
        v = edge[i].v;
        if((dpth[v]==dpth[u]+1)&&edge[i].w!=0)
        {
            int di = dfs(v,min(dist,edge[i].w));
            if(di>0){
                edge[i].w-=di;
                edge[i^1].w+=di;
                return di;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs())
        while(int di = dfs(s,INF))
            ans+=di;
    return ans;
}
bool link[M];
int a[M];
int main()
{
    int n,m;
    scanf("%d",&n);
    init();
    s = n+1,t = n+2;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(__builtin_popcount(a[i])&1)link[i] = true;
        if(link[i])add(s,i,1);
        else add(i,t,1);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(__builtin_popcount(a[i]^a[j])==1){
                if(link[i])add(i,j,1);
                else add(j,i,1);
            }
        }
    }
    int ans = n - dinic();
    printf("%d\n",ans);
    for(int i=1;i<=n;i++){
        if(dpth[i]!=0&&link[i])printf("%d ",a[i]);
        else if(dpth[i]==0&&!link[i])printf("%d ",a[i]);
    }
    return 0;
}