BZOJ4536 : 最大異或和II

建立$n+m$個點的無向圖，其中$n$個點表示輸入的數列，$m$個點表示答案的$m$個二進制位。

對于輸入的兩個數$a[i],a[j]$，若它們存在公共二進制位，則可以通過同時選某一公共位來對答案貢獻$0$，并完成兩個數的選擇，因此在數$i$和數$j$之間連邊，邊權為二維權值$(2,0)$。
對于輸入的某個數$a[i]$，若它二進制下第$j$位為$1$，則可以通過讓它選這一位來對答案貢獻$2^j$，因此在數$i$和位$j$之間連邊，邊權為二維權值$(1,2^j)$。

顯然每個點最多只允許匹配一次，目標就是最大化二維權值的總和，即先保證$n$個數都完成了選擇，再最大化每一位選擇個數為奇數的貢獻和。

利用一般圖最大權匹配算法求出答案即可。

時間復雜度$O((n+m)^3)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1023;
struct Num{
  int a;ll b;
  Num(){a=b=0;}
  Num(int _a,ll _b){a=_a;b=_b;}
  Num operator+(const Num&p)const{return Num(a+p.a,b+p.b);}
  Num operator-(const Num&p)const{return Num(a-p.a,b-p.b);}
  Num operator*(int p)const{return Num(a*p,b*p);}
  Num operator/(int p)const{return Num(a/p,b/p);}
  void operator+=(const Num&p){a+=p.a;b+=p.b;}
  void operator-=(const Num&p){a-=p.a;b-=p.b;}
  bool operator<(const Num&p)const{
    if(a!=p.a)return a<p.a;
    return b<p.b;
  }
  bool operator>(const Num&p)const{
    if(a!=p.a)return a>p.a;
    return b>p.b;
  }
  bool operator<=(const Num&p)const{
    if(a!=p.a)return a<p.a;
    return b<=p.b;
  }
  bool operator==(const Num&p)const{return a==p.a&&b==p.b;}
};
const Num INF(1e9,4e18),ZERO(0,0);
struct Edge{
  int u,v;Num w;
  Edge(){}
  Edge(int _u,int _v,const Num&_w){u=_u,v=_v,w=_w;}
}g[N][N];
int n,n_x,match[N],slack[N],st[N],pa[N],flower_from[N][N],S[N],vis[N];
Num lab[N];
vector<int> flower[N];
deque<int> q;
inline Num DIST(const Edge&e){return lab[e.u]+lab[e.v]-g[e.u][e.v].w*2;}
inline void update_slack(int u,int x){
  if(!slack[x]||DIST(g[u][x])<DIST(g[slack[x]][x]))slack[x]=u;
}
inline void set_slack(int x){
  slack[x]=0;
  for(int u=1; u<=n; ++u)
    if(g[u][x].w>ZERO&&st[u]!=x&&S[st[u]]==0)update_slack(u,x);
}
inline void q_push(int x){
  if(x<=n)return q.push_back(x);
  for(int i=0; i<flower[x].size(); i++)q_push(flower[x][i]);
}
inline void set_st(int x,int b){
  st[x]=b;
  if(x<=n)return;
  for(int i=0; i<flower[x].size(); ++i)set_st(flower[x][i],b);
}
inline int get_pr(int b,int xr){
  int pr=find(flower[b].begin(),flower[b].end(),xr)-flower[b].begin();
  if(pr%2==1){
    reverse(flower[b].begin()+1,flower[b].end());
    return (int)flower[b].size()-pr;
  }
  else return pr;
}
inline void set_match(int u,int v){
  match[u]=g[u][v].v;
  if(u<=n)return;
  Edge e=g[u][v];
  int xr=flower_from[u][e.u],pr=get_pr(u,xr);
  for(int i=0; i<pr; ++i)set_match(flower[u][i],flower[u][i^1]);
  set_match(xr,v);
  rotate(flower[u].begin(),flower[u].begin()+pr,flower[u].end());
}
inline void augment(int u,int v){
  int xnv=st[match[u]];
  set_match(u,v);
  if(!xnv)return;
  set_match(xnv,st[pa[xnv]]);
  augment(st[pa[xnv]],xnv);
}
inline int get_lca(int u,int v){
  static int t=0;
  for(++t; u||v; swap(u,v)){
    if(u==0)continue;
    if(vis[u]==t)return u;
    vis[u]=t;
    u=st[match[u]];
    if(u)u=st[pa[u]];
  }
  return 0;
}
inline void add_blossom(int u,int lca,int v){
  int b=n+1;
  while(b<=n_x&&st[b])++b;
  if(b>n_x)++n_x;
  lab[b]=ZERO;
  S[b]=0;
  match[b]=match[lca];
  flower[b].clear();
  flower[b].push_back(lca);
  for(int x=u,y; x!=lca; x=st[pa[y]])
    flower[b].push_back(x),flower[b].push_back(y=st[match[x]]),q_push(y);
  reverse(flower[b].begin()+1,flower[b].end());
  for(int x=v,y; x!=lca; x=st[pa[y]])
    flower[b].push_back(x),flower[b].push_back(y=st[match[x]]),q_push(y);
  set_st(b,b);
  for(int x=1; x<=n_x; ++x)g[b][x].w=g[x][b].w=ZERO;
  for(int x=1; x<=n; ++x)flower_from[b][x]=0;
  for(int i=0; i<flower[b].size(); ++i){
    int xs=flower[b][i];
    for(int x=1; x<=n_x; ++x)
      if(g[b][x].w==ZERO||DIST(g[xs][x])<DIST(g[b][x]))
        g[b][x]=g[xs][x],g[x][b]=g[x][xs];
    for(int x=1; x<=n; ++x)
      if(flower_from[xs][x])flower_from[b][x]=xs;
  }
  set_slack(b);
}
inline void expand_blossom(int b){
  for(int i=0; i<flower[b].size(); ++i)
    set_st(flower[b][i],flower[b][i]);
  int xr=flower_from[b][g[b][pa[b]].u],pr=get_pr(b,xr);
  for(int i=0; i<pr; i+=2){
    int xs=flower[b][i],xns=flower[b][i+1];
    pa[xs]=g[xns][xs].u;
    S[xs]=1,S[xns]=0;
    slack[xs]=0,set_slack(xns);
    q_push(xns);
  }
  S[xr]=1,pa[xr]=pa[b];
  for(int i=pr+1; i<flower[b].size(); ++i){
    int xs=flower[b][i];
    S[xs]=-1,set_slack(xs);
  }
  st[b]=0;
}
inline bool on_found_Edge(const Edge &e){
  int u=st[e.u],v=st[e.v];
  if(S[v]==-1){
    pa[v]=e.u,S[v]=1;
    int nu=st[match[v]];
    slack[v]=slack[nu]=0;
    S[nu]=0,q_push(nu);
  }
  else if(S[v]==0){
    int lca=get_lca(u,v);
    if(!lca)return augment(u,v),augment(v,u),1;
    else add_blossom(u,lca,v);
  }
  return 0;
}
inline void umin(Num&a,const Num&b){if(a>b)a=b;}
inline bool matching(){
  fill(S,S+n_x+1,-1),fill(slack,slack+n_x+1,0);
  q.clear();
  for(int x=1; x<=n_x; ++x)
    if(st[x]==x&&!match[x])pa[x]=0,S[x]=0,q_push(x);
  if(q.empty())return 0;
  for(;;){
    while(q.size()){
      int u=q.front();
      q.pop_front();
      if(S[st[u]]==1)continue;
      for(int v=1; v<=n; ++v)
        if(g[u][v].w>ZERO&&st[u]!=st[v]){
          if(DIST(g[u][v])==ZERO){
            if(on_found_Edge(g[u][v]))return 1;
          }
          else update_slack(u,st[v]);
        }
    }
    Num d=INF;
    for(int b=n+1; b<=n_x; ++b)
      if(st[b]==b&&S[b]==1)umin(d,lab[b]/2);
    for(int x=1; x<=n_x; ++x)
      if(st[x]==x&&slack[x]){
        if(S[x]==-1)umin(d,DIST(g[slack[x]][x]));
        else if(S[x]==0)umin(d,DIST(g[slack[x]][x])/2);
      }
    for(int u=1; u<=n; ++u){
      if(S[st[u]]==0){
        if(lab[u]<=d)return 0;
        lab[u]-=d;
      }
      else if(S[st[u]]==1)lab[u]+=d;
    }
    for(int b=n+1; b<=n_x; ++b)
      if(st[b]==b){
        if(S[st[b]]==0)lab[b]+=d*2;
        else if(S[st[b]]==1)lab[b]-=d*2;
      }
    q.clear();
    for(int x=1; x<=n_x; ++x)
      if(st[x]==x&&slack[x]&&st[slack[x]]!=x&&DIST(g[slack[x]][x])==ZERO)
        if(on_found_Edge(g[slack[x]][x]))return 1;
    for(int b=n+1; b<=n_x; ++b)
      if(st[b]==b&&S[b]==1&&lab[b]==ZERO)expand_blossom(b);
  }
  return 0;
}
inline pair<Num,int> weight_blossom(){
  fill(match,match+n+1,0);
  n_x=n;
  int n_matches=0;
  Num tot_weight=ZERO;
  for(int u=0; u<=n; ++u)st[u]=u,flower[u].clear();
  Num w_max=ZERO;
  for(int u=1; u<=n; ++u)
    for(int v=1; v<=n; ++v){
      flower_from[u][v]=(u==v?u:0);
      w_max=max(w_max,g[u][v].w);
    }
  for(int u=1; u<=n; ++u)lab[u]=w_max;
  while(matching())++n_matches;
  for(int u=1; u<=n; ++u)
    if(match[u]&&match[u]<u)
      tot_weight+=g[u][match[u]].w;
  return make_pair(tot_weight,n_matches);
}
ll a[N];
inline void add(int u,int v,const Num&w){g[u][v].w=g[v][u].w=w;}
int main(){
  int Case,_n,_m;
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&_n);
    _m=60;
    n=_n+_m;
    for(int u=1; u<=n; ++u)
      for(int v=1; v<=n; ++v)
        g[u][v]=Edge(u,v,ZERO);
    for(int i=1;i<=_n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=_n;i++){
      for(int j=0;j<_m;j++)if(a[i]>>j&1)add(i,_n+j+1,Num(1,1LL<<j));
      for(int j=1;j<i;j++)if(a[i]&a[j])add(i,j,Num(2,0));
    }
    pair<Num,int>ans=weight_blossom();
    printf("%lld\n",ans.first.b);
  }
  return 0;
}

posted @ 2022-12-12 22:09 Claris 閱讀(225) 評論(0) 收藏舉報

刷新頁面返回頂部

Claris' Blog

BZOJ4536 : 最大異或和II

公告