用二分图求最大独立集
<pre><code>#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
const int maxn = 5005;
unordered_map<int, int> mp;
vector<int> v, c, z;
vector<int> vec[maxn];
int data[maxn], index[maxn];
int pre[maxn], vis[maxn];
bool used[maxn];
int n, cnt, ans;
void dfs(int u, int fa, int t){
used[u] = true;
if(t == 1) v.push_back(u);
else z.push_back(u);
for(int i = 0; i < vec[u].size(); i++){
int v = vec[u][i];
if(v == fa || used[v]) continue;
dfs(v, u, t^1);
}
}
bool found(int u, int t){
vis[u] = t;
for(int i = 0; i < vec[u].size(); i++){
int v = vec[u][i];
if(vis[v] == t) continue;
vis[v] = t;
if(pre[v] == 0 || found(pre[v], t)){
pre[v] = u;
pre[u] = v;
return true;
}
}
return false;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
scanf("%d", &data[i]);
mp[data[i]] = ++cnt, index[cnt] = data[i];
}
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
int now = (data[i] ^ data[j]);
if((now & (now-1)) == 0){
vec[mp[data[i]]].push_back(mp[data[j]]);
vec[mp[data[j]]].push_back(mp[data[i]]);
}
}
}
for(int i = 1; i <= cnt; i++){
if(!used[i]) dfs(i, 0, 1);
}
for(int i = 0; i < v.size(); i++){
if(found(v[i], i+1)) ans++;
}
printf("%d\n", cnt-ans);
for(int i = 1; i <= cnt; i++) vis[i] = 0;
for(int i = 0; i < v.size(); i++){
if(!pre[v[i]]) found(v[i], 1);
}
for(int i = 0; i < v.size(); i++){
if(vis[v[i]]) printf("%d ", index[v[i]]);//左边标记的
}
for(int i = 0; i < z.size(); i++){
if(!vis[z[i]]) printf("%d ", index[z[i]]);//右边未标记的
}
}</code></pre>