1572D - Bridge Club - CodeForces Solution

#include<bits/stdc++.h>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define P std::pair
#define MP std::make_pair
#define pb emplace_back
const int N=15607,M=1048577,K=10485767,INF=0x7fffffff;

struct Edge{
	int u,v,c;
}edges[K];
int cnt=0;
bool cmp(Edge a,Edge b){
	return a.c>b.c;
}
struct Node{
	int v,w,c,r;
};
std::vector<Node>b[N];
inline void add(int u,int v,int w,int c){
	b[u].pb(Node{v,w,c,b[v].size()});
	b[v].pb(Node{u,0,-c,b[u].size()-1});
}
int n,k,a[M],refer[M],id=3;
int flow[N],inq[N],dis[N],last[N];
std::queue<int>q;
bool SPFA(){
	FOR(i,1,id)flow[i]=-1,last[i]=-1,dis[i]=-INF;
	q.push(1);
	flow[1]=INF;dis[1]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		inq[u]=0;
		for(Node i:b[u]){
			if(i.w>0&&dis[i.v]<dis[u]+i.c){
				dis[i.v]=dis[u]+i.c;
				flow[i.v]=std::min(flow[u],i.w);
				last[i.v]=i.r;
				if(!inq[i.v]){q.push(i.v);inq[i.v]=1;}
			}
		}
	}
	return last[3]!=-1;
}

int maxcost(){
	int ans=0;
	while(SPFA()){
		ans+=flow[3]*dis[3];
		for(int i=3;i!=1;i=b[i][last[i]].v){
			Node &j=b[i][last[i]];
			j.w+=flow[3],b[j.v][j.r].w-=flow[3];
		}
	}
	return ans;
}

signed main(){
    std::cin.tie(0)->sync_with_stdio(0);
    std::cin>>n>>k;
    int t=(1<<n)-1,require=(k-1)*(2*n-1)+1;
	FOR(i,0,t)std::cin>>a[i];
	FOR(i,0,t)if(__builtin_popcount(i)&1)FOR(j,0,n-1){
		int x=i^(1<<j);
		edges[++cnt]={i,x,a[i]+a[x]};
	}
	if(require>=cnt)require=cnt;
	else std::nth_element(edges+1,edges+1+require,edges+1+cnt,cmp);
	add(1,2,k,0);
	FOR(i,1,require){
		int u=edges[i].u,v=edges[i].v,c=edges[i].c;
		if(refer[u]==0)refer[u]=++id;
		if(refer[v]==0)refer[v]=++id;
		add(refer[u],refer[v],1,c);
	}
	FOR(i,0,t){
		if(refer[i]){
			if(__builtin_popcount(i)&1)add(2,refer[i],1,0);
			else add(refer[i],3,1,0);
		}
	}
	std::cout<<maxcost();
    return 0;
}