本文共 2133 字，大约阅读时间需要 7 分钟。
大意: 给定$n$个互不相同的数, 若两个数异或后二进制中$1$的个数不少于$2$则连边, 求最大团.
最大团转为补图最大独立集. 可以发现补图是二分图, 所以直接$dinic$即可.
最大独立集相当于n-最小割, 最终$X$部仍与$S$相连的点和$Y$部不与$S$相连的点构成最大独立集.
#include #include #include #include #include #include #include #include #include #include #include #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< <<' ';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 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;}
转载于:https://www.cnblogs.com/uid001/p/11285417.html