[ABC190E] Magical Ornament 题解

Jia_ye · 2022-12-22 14:52:51 · 题解

因为写位运算不熟练，而且想按秩转移的时候总是头疼，所以写了题解记录一下。

AtCoder 王国流通着 N 种魔法石，编号为 1,2,\dots,N。高桥想要把魔法石排成一列做成装饰品。
有的魔法石能够相邻放在一起，有的魔法石却不行。有 M 组魔法石是可以相邻的，分别是 ( 魔法石 A_1, 魔法石 B_1),\ ( 魔法石 A_2, 魔法石 B_2),\ \dots,\ ( 魔法石 A_M, 魔法石 B_M) 。除此之外的任何两个魔法石都不能相邻摆放。（可以相邻的魔法石摆放前后顺序不限。）
请判断是否存在这样一种排列方式，使得其中包含 C_1,C_2,\dots,C_K 中的每一种魔法石。如果存在，求形成这样一个序列所需的最小宝石数量。如果不存在的话，输出 -1。

（这个翻译也可以考虑采纳XD）

注意到合法序列的每一个石头前后的石头都是必须满足和自己能相邻的，所以这道题能转化为一道图论题。在可以每个可以相邻的 A_i 和 B_i 建立一条长度为 1 的边，于是问题就转化为寻找一个遍历 C_1 到 C_K 每一个点的最短路。此外如果这些点中有点不与图连通，那就没有合法路径。

注意到 1\le K\le 17 的小范围，可以把 C_i 是否为在路径上的路径情况表示成二进制数 S。考虑状态压缩的动态规划。定义 f_{i,S} 为以 C_i 结尾的、拥有 C_1 到 C_K 中的点的集合为 S 的最短路径。于是答案为所有 i 中最短的路径长度再加 1，即 \min\limits_{i=1,2,\dots,N}\{f_{i,2^K-1}\}+1，注意加 1 是因为要求的是序列长度，路径长度只是两点间隔数。

考虑转移。如果 j 在集合 S 中，那么 C_j 就可以作为序列中的一个数。于是对于每一个集合 S 中的 j，都可以转移到 i。即

f_{i,S}=\min_{j\in S}\{f_{j,S-\{j\}}+dis_{i,C_j}\}

按秩转移的话就得倒过来想。如果与 i 相邻的点 j 不在目前的集合中，那么就可以转移到 j。从点 i 开始 DFS，因为我们以 i 为结尾定义的 f 嘛，所以可以理解为往前转移，直到搜到 S=2^K-1 停止并回溯。

[评测记录](https://atcoder.jp/contests/abc190/submissions/37418596) $\mathtt{275ms/98204KB/1250B}

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int inf=1e9;
const int maxn=1e5+9;
const int maxk=20;

vector<int> G[maxn];
void add(int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

int c[maxk];
int n,m,k;
int dis[maxk][maxn];

void bfs(int p)
{
    for(int i=1;i<=n;i++)
        dis[p][i]=inf;

    queue<int> q;
    dis[p][c[p]]=0;
    q.push(c[p]);

    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(auto v:G[u])
        {
            if(dis[p][v]==inf)
            {
                dis[p][v]=dis[p][u]+1;
                q.push(v);
            }
        }
    }
}

int f[maxk][(1<<maxk)];
int dp(int i,int s)
{
    if(s==(1<<k)-1)
        return 0;

    if(f[i][s]!=-1)
        return f[i][s];

    f[i][s]=inf;
    for(int j=0;j<k;j++)
    {
        if(s&(1<<j))
            continue;
        f[i][s]=min(f[i][s],dp(j,s|(1<<j))+dis[j][c[i]]);
    }
    return f[i][s];
}

int main()
{
    memset(f,-1,sizeof(f));

    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y; cin>>x>>y;
        add(x,y);
    }

    cin>>k;
    for(int i=0;i<k;i++)
        cin>>c[i];
    for(int i=0;i<k;i++)
        bfs(i);

    for(int i=0;i<k;i++)
        if(dis[i][c[0]]==inf)
            return cout<<-1<<endl,0;

    int ans=inf;
    for(int i=0;i<k;i++)
        ans=min(ans,dp(i,1<<i)+1);
    cout<<ans<<endl;

    return 0;
}