牛客2019多校第五场maximum clique 1(隐含二分图最大团)

以前还是对最大独立集之类的东西概念混淆不清,搞得我看了很久…

要求找出最大团,使得任意两个数二进制至少有2位不同

这是个二分图.

$我们按照二进制1的奇偶性可以分为两个集合$

$若同为为奇数(或偶数),不管怎么构造,都至少有2位不同$

$因为数字互不相同,所以即使1的个数相同,也会有2位不同$

那么最大团=二分图补集的最大独立集

$补图就是恰好有1位二进制不同$

$那么把1个数是奇数放左边,偶数放右边$

$裸题了$

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
int n,m,s,t,a[maxn],color[maxn],dis[maxn];
int lowbit(int x){return x&(-x);
}
struct edge{int to,nxt,flow;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int flow){d[++cnt]=(edge){v,head[u],flow},head[u]=cnt;d[++cnt]=(edge){u,head[v],0},head[v]=cnt;
}
void connect(int q,int w)
{if( color[q]>color[w] )	swap(q,w);add(q,w,1);
}
bool bfs()
{for(int i=0;i<=t;i++)	dis[i]=0;dis[s]=1;queue<int>q; q.push( s );while( !q.empty() ){int u=q.front(); q.pop();for(int i=head[u];i;i=d[i].nxt ){int v=d[i].to;if( d[i].flow&&dis[v]==0 ){dis[v]=dis[u]+1;if( v==t )	return true;q.push( v );}}}return false;
}
int dinic(int u,int flow)
{if( u==t )	return flow;int res=flow;for(int i=head[u];i&&res;i=d[i].nxt ){int v=d[i].to;if( dis[v]==dis[u]+1&&d[i].flow){int temp=dinic(v,min(res,d[i].flow) );if( temp==0 )	dis[v]=0;res-=temp;d[i].flow-=temp;d[i^1].flow+=temp;}}return flow-res;
}
int main()
{cin >> n;for(int i=1;i<=n;i++)	cin >> a[i],color[i]=__builtin_popcount(a[i])%2;	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){int x=a[i]^a[j];if( lowbit(x)==x )//恰好1位不同connect(i,j); }s=0,t=n+1;for(int i=1;i<=n;i++){if( !color[i] )	add(s,i,1);else	add(i,t,1);}int ans=0;while( bfs() )	ans+=dinic(s,inf);cout << n-ans << endl;for(int i=1;i<=n;i++){if( color[i]%2==0&&dis[i] )	cout << a[i] << " ";if( color[i]%2==1&&!dis[i] )	cout << a[i] << " ";}
}