2019牛客暑假多校訓練賽第五場F題 maximum clique 1 （最大團，補圖最大獨立集）

題目連結：https://ac.nowcoder.com/acm/contest/885/F

題意：給出n個數，且每個數都不同，要求找出最多的一個子集使得其中任意兩個數的二進制位至少有兩個不同，并輸出這個集合

資料範圍：1≤N≤5000, 1≤ai≤1e9

思路:首先把這n個數按照二進制位裡1的個數分為奇數個1和偶數個1的集合，對于奇數個1的集合裡任意兩個數都是滿足至少有兩位二進制位不同的，偶數個1的集合裡同理。那麼隻需要去掉奇數個1和偶數個1的集合裡那些是不能的同時出現的其中一個即可。

這時候我們隻需按照不同二進制位個數大于等于2的數兩兩連邊，求一個原圖的最大團（及一個最大完全圖）即可，然而我們知道最大團等于補圖的最大獨立集，最大獨立集=n-最大比對。這是時候我們隻需求按照二進制位隻有一位不同的點去連邊即可，而這些邊正好構成了上面說的奇數集合和偶數集合的一個二分圖，這時求出最大比對，輸出時把沒有比對的點輸出和比對上的點去掉一半輸出。

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5;
map<int,int>mp;
int head[N],cnt,tot,n,m,cx[N],cy[N],a[N],b[N],v;
bool vis[N];
struct Edge{int to,next;}edge[N*N];
void add(int u,int v){
	edge[cnt]={v,head[u]};
	head[u]=cnt++;
}
bool dfs(int u){///匈牙利
	vis[u]=1;
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(!vis[v]){
			vis[v]=1;
			if(cy[v-n]==-1||dfs(cy[v-n])){
				cx[u]=v-n;
				cy[v-n]=u;
				return 1;
			}
		}
	}
	return 0;
}
int hungary(){///匈牙利
	int res=0;
	memset(vis,0,sizeof vis);
	memset(cx,-1,sizeof cx);
	memset(cy,-1,sizeof cy);
	for(int u=1;u<=n;u++){
		memset(vis,0,sizeof vis);
		res+=dfs(u);
	}
	return res;
}
void MaxIndependentSet(){///最大獨立集用匈牙利跑輸出路徑
	memset(vis,0,sizeof vis);
	///與左面的沒有比對上的點有相連性質的右面的點要标記上，最後不輸出這些點
	///對于沒有比對上的點，與它們相連的邊比較少這樣标記的點也少
	for(int i=1;i<=n;i++)if(cx[i]==-1)dfs(i);
	for(int i=1;i<=n;i++)if(vis[i])printf("%d ",a[i]);
	for(int i=n+1;i<=n+m;i++)if(!vis[i])printf("%d ",b[i-n]);
	puts("");
	///左面标記的輸出，右面未标記的輸出
	///太菜了，隻會先跑匈牙利，在對沒比對上的邊反跑才會求最大獨立集
}
int main(){
    scanf("%d",&tot);
	memset(head,-1,sizeof head);cnt=0;
    for(int i=1;i<=tot;i++){
    	scanf("%d",&v);
    	int num=0,tmp=v;
    	for(;tmp;tmp>>=1)if(tmp&1)num++;
    	if(num&1)a[++n]=v;///奇數個1的數
    	else b[++m]=v;///偶數個1的數
    }
    for(int i=1;i<=m;i++)mp[b[i]]=n+i;///b[i]的實際點為n+i
	for(int i=1;i<=n;i++){
		for(int j=0;j<32;j++){///補圖
			if(mp.count(a[i]^(1<<j))){
				add(i,mp[a[i]^(1<<j)]);
			}
		}
	}
	printf("%d\n",tot-hungary());
	MaxIndependentSet();///最大獨立集
	return 0;
}