题解：P16153 [ICPC 2016 NAIPC] Fancy Antiques

· · 题解

题意简述

每件古董可在两个指定商店分别以给定价格购买。访问不超过 k 家商店，求买齐全部古董的最小费用；若无法买齐则输出 -1。

解题思路

把商店视为点，每件古董连接出售其两个版本的商店。设 T 为未访问商店的集合。若某件古董的两个商店都属于 T，该古董便无法购买，因此 T 必须是独立集。若两个版本位于同一家商店，则该商店不能属于 T。

考虑两个版本位于不同商店的一件古董。设其商店分别为 u,v，价格分别为 p,q。先把 \min(p,q) 加入固定费用。若 u 未访问，则只能在 v 购买，费用增加 q-\min(p,q)；若 v 未访问，则费用增加 p-\min(p,q)。独立集不可能同时包含 u,v，故可将这两项增量分别计入点 u,v 的权值。所有点权均非负。

访问不超过 k 家商店等价于 |T|\ge m-k。若可行集合包含更多点，删去若干点后仍为独立集，且总权值不会增加。因此仅需求大小恰为 r=m-k 的最小权独立集。

将 m 个点分成大小不超过 20 的两部分。枚举右部所有子集，记录其是否为独立集、点权和与大小。令 f_{s,X} 表示可选掩码 X 中，大小为 s 的独立子集的最小权值。初始时仅将每个独立集写入对应状态。再对每个掩码中存在的位 j 做子集最小值变换：

f_{s,X}\gets\min(f_{s,X},f_{s,X-2^j})

变换后，枚举每个合法的左部独立集 L。删去右部所有与 L 相邻的点，得到可选掩码 X，再用 f_{r-|L|,X} 补足右部点数。任意大小为 r 的合法独立集都能唯一拆成这种左右组合；右部查询又排除了全部跨部冲突，故枚举恰好覆盖所有可行解。

时间复杂度为 O(m^2\cdot2^{m/2})，空间复杂度为 O(m2^{m/2})。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=45;
const int K=25;
const int S=1<<20;
const int inf=0x3f3f3f3f;
ll G[N];
int w[N],f[K][S],sum[S],nb[S];
bool ok[S];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,r;
    cin>>n>>m>>r;
    int ans=0;
    ll ban=0;
    for(int i=1;i<=n;i++)
    {
        int a,p,b,q;
        cin>>a>>p>>b>>q;
        a--;b--;
        ans+=min(p,q);
        if(a==b)ban|=1LL<<a;
        else
        {
            G[a]|=1LL<<b;
            G[b]|=1LL<<a;
            w[a]+=max(q-p,0);
            w[b]+=max(p-q,0);
        }
    }
    int a=m/2,b=m-a;
    int lim=1<<b;
    for(int i=0;i<K;i++)fill(f[i],f[i]+lim,inf);
    ok[0]=1;
    f[0][0]=0;
    for(int i=1;i<lim;i++)
    {
        int j=__builtin_ctz((unsigned)i),t=i&(i-1);
        ok[i]=ok[t]&&!((ban>>a>>j)&1)&&!((G[a+j]>>a)&t);
        sum[i]=sum[t]+w[a+j];
        if(ok[i])f[__builtin_popcount((unsigned)i)][i]=sum[i];
    }
    r=m-r;
    for(int i=0;i<=min(b,r);i++)
    {
        for(int j=0;j<b;j++)
        {
            for(int k=0;k<lim/2;k++)
            {
                int t=(k&((1<<j)-1))|(k>>j<<(j+1))|(1<<j);
                f[i][t]=min(f[i][t],f[i][t^(1<<j)]);
            }
        }
    }
    lim=1<<a;
    ok[0]=1;
    sum[0]=0;
    nb[0]=0;
    int res=inf;
    for(int i=0;i<lim;i++)
    {
        if(i)
        {
            int j=__builtin_ctz((unsigned)i),t=i&(i-1);
            ok[i]=ok[t]&&!((ban>>j)&1)&&!(G[j]&t);
            sum[i]=sum[t]+w[j];
            nb[i]=nb[t]|int(G[j]>>a);
        }
        int j=__builtin_popcount((unsigned)i);
        if(ok[i]&&j<=r&&r-j<=b)res=min(res,sum[i]+f[r-j][(1<<b)-1&~nb[i]]);
    }
    cout<<(res==inf?-1:ans+res)<<'\n';
    return 0;
}