大意: 给定$n$个互不相同的数, 若两个数异或后二进制中$1$的个数不少于$2$则连边, 求最大团.

最大团转为补图最大独立集. 可以发现补图是二分图, 所以直接$dinic$即可.

最大独立集相当于n-最小割, 最终$X$部仍与$S$相连的点和$Y$部不与$S$相连的点构成最大独立集.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n, a[N], b[N];
struct edge {
int to,w,next;
edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
REP(i,1,n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
dep[S]=INF,vis[S]=0,cur[S]=head[S];
dep[T]=INF,vis[T]=0,cur[T]=head[T];
dep[S]=0,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
for (int i=head[u]; i; i=e[i].next) {
if (dep[e[i].to]>dep[u]+1&&e[i].w) {
dep[e[i].to]=dep[u]+1;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = 0;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+1&&e[i].w) {
int f = dfs(e[i].to,min(w-used,e[i].w));
if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = 0;
while (bfs()) ans+=dfs(S,INF);
return ans;
}
void add(int u, int v, int w) {
e[++cnt] = edge(v,w,head[u]);
head[u] = cnt;
e[++cnt] = edge(u,0,head[v]);
head[v] = cnt;
} int main() {
scanf("%d", &n);
REP(i,1,n) {
scanf("%d",a+i);
b[i] = __builtin_parity(a[i]);
if (b[i]) add(S,i,1);
else add(i,T,1);
}
REP(i,1,n) REP(j,i+1,n) {
int x = a[i]^a[j];
if ((x&(x-1))==0) {
if (b[i]) add(i,j,INF);
else add(j,i,INF);
}
}
printf("%d\n",n-dinic());
REP(i,1,n) if ((dep[i]==INF)^b[i]) printf("%d ", a[i]);hr;
}

最新文章

  1. JavaScript 控制字体大小设置
  2. git命令大集合
  3. 如何在HTML中加载Flash(2种实现方法)_HTML/Xhtml_网页制作
  4. Python数据类型之“序列概述与基本序列类型(Basic Sequences)”
  5. NYOJ题目1048破门锁
  6. Java NIO之缓冲区Buffer
  7. docker-registry使用笔记
  8. HttpCache ETag与Last-Modified与Expires
  9. CSS样式的面向对象思想(一)
  10. [Netty 1] 初识Netty
  11. scrapy写爬虫是出现no module named win32api错误
  12. UVA 11402 - Ahoy, Pirates!(段树)
  13. uvalive 3135 Argus
  14. OVF文件考究
  15. (转)Jquery获取上级、下级或者同级的元素
  16. SVN服务器本地搭建与使用
  17. Sitecore Aliases
  18. [ 转载 ]Java:成员变量,局部变量,静态变量的区别
  19. 安装Redis的PHP扩展
  20. RFID-RC522 与Arduino的连接

热门文章

  1. ActiveMQ相关API
  2. Android命名规范(重点讲解:包名)
  3. 006 GET API
  4. 开源社区人们总说的LGTM是什么意思?
  5. ISO/IEC 9899:2011 条款6.5——表达式
  6. SAP 增强篇 Method1 BADI增强的查找方法
  7. SignalR 传Model类型的参数
  8. 【ARTS】01_43_左耳听风-201900902~201900908
  9. iOS-关于创建真机调试证书(发布证书,测试证书,推送调试证书)【转】
  10. 文件描述符FD的含义/文件句柄