CF1572D 题解

· · 题解

CF1572D Brifge Club

题意

有 2^n 个点从 0 到 2^n-1 编号，每个点有点权。

若两个点 u 和 v 有且仅有一个二进制位不同，则两点之间有边。

要求从这个图中选一个最多 k 条边的匹配，使其所包含的 2k 个点点权和最大。

输出最大点权和。

思路

首先发现，如果两点间有边，则一个点编号二进制下 1 的个数为奇数，另一个点编号二进制下 1 的个数为偶数。

所以想到按编号二进制下 1 的个数的奇偶分类，然后将 i 向 i\ \mathrm{xor} 2^j 连边 (j \in 1\sim n-1)。

然后发现这是一个二分图，边权为两个端点的权值和。

问题转化为在二分图上找包含 k 条边的最大权匹配。

一开始想抽象建图跑最大流，但是发现不是太好做，于是考虑费用流。

因为边权只能计算一次，每个点也只能经过一次，所以容量均为 1，费用为端点的点权和，超级源点/汇点与点的连边费用为 0。

这样跑最大费用最大流，找到 k 条增广路即可。

(不知道为啥我的最大费用最大流挂了，所以把费用取反，跑的最小费用最大流......)

但是，发现这样复杂度是过不了的，因为边数、点数实在是太多了。

由于我们要找的是一个包含 k 条边的最大权匹配，那么有一些权值较小的边是不需要的。

因为求的是匹配，所以选中一条边后，有一些边就不可能再选了。

由于一个点会作为 n 条边的端点，所以选中一条边后会有 2n-2 条边无法再选。

所以只需要考虑权值前 2nk 大的边即可。

时间复杂度 O(n2^n+nk^2\log(nk))。

code

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N=(1<<20)+10,inf=1e18;
int ans,n,k,s,t,a[N],tot,tott=1,dis[N],vis[N],cur[N],h[N],cntt,tmp;
struct node{
    int u,v,w;
}e[N*20];
struct Node{
    int nxt,to,w,c;
}E[N];
void add(int u,int v,int w){
    e[++tot]={u,v,w};
}
void ad(int u,int v,int w,int c){
    E[++tott]={h[u],v,w,c};
    h[u]=tott;
}
int spfa(){
    for(int i=0;i<=t;i++){
        dis[i]=inf;
        cur[i]=h[i];
        vis[i]=0;
    }
    queue<int> q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=E[i].nxt){
            int v=E[i].to,w=E[i].w,c=E[i].c;
            if(dis[v]<=dis[u]+c||w==0) continue;
            dis[v]=dis[u]+c;
            if(!vis[v]){
                q.push(v);
                vis[v]=1;
            }
        }
    }
    return dis[t]!=inf;
}
int dfs(int u,int fl){
    if(u==t) return fl;
    int res=fl;
    vis[u]=1;
    for(int &i=cur[u];i;i=E[i].nxt){
        int v=E[i].to,w=E[i].w,c=E[i].c;
        if(dis[v]!=dis[u]+c||w==0||vis[v]) continue;
        int flow=dfs(v,min(res,w));
        if(flow){
            res-=flow;
            E[i].w-=flow;
            E[i^1].w+=flow;
            if(res<=0) break;
        }
    }
    return fl-res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>k;
    s=(1<<n),t=(1<<n)+1;
    for(int i=0;i<=(1<<n)-1;i++)
        cin>>a[i];
    for(int i=0;i<=(1<<n)-1;i++){
        int cnt=__builtin_popcount(i);
        if(__builtin_popcount(i)&1){
            for(int j=0;j<n;j++){
                int o=i^(1<<j);
                add(i,o,a[i]+a[o]);
            }
        }
    }
    sort(e+1,e+tot+1, [](node a,node b){
        return a.w>b.w;
    });
    for(int i=1;i<=2*n*k;i++){
        ad(e[i].u,e[i].v,1,-e[i].w);
        ad(e[i].v,e[i].u,0,e[i].w);
        if(!mp[e[i].u]){
            ad(s,e[i].u,1,0);
            ad(e[i].u,s,0,0);
            mp[e[i].u]=1;
        }
        if(!mp[e[i].v]){
            ad(e[i].v,t,1,0);
            ad(t,e[i].v,0,0);
            mp[e[i].v]=1;
        }
    }
    while(spfa()){
        int flow=dfs(s,inf);
        if(tmp+flow>k){
            ans+=(k-tmp)*dis[t];
            break;
        }
        ans+=flow*dis[t];
        tmp+=flow;
    }
    cout<<-ans<<'\n';
}
//3 3
//10 5 4 10 4 8 5 5