[ABC190E] Magical Ornament 题解

题目链接：[ABC190E] Magical Ornament

题意：

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。

$1 \le N,M \le 10^5,1\le K\le 17,1\le C_i < C_{i+1} \le N$

把 $m$ 组条件看作 $A_i$ 向 $B_i$ 的一条双向边，则题目需要我们找到一条最短路径，

使得 $C_1$ 到 $C_k$ 的每一个点都包含在路径中，显然这条路径很不一定是简单路径。

又因为 $k$ 的范围很小，那么我们不妨考虑状压dp。

记 $f_{i,S}$ 表示以 $C_i$ 为结尾且状态为 $S$ 时的最短路径，其中 $S$ 表示包含了哪些 $C$ 在这条路径上，则

$$f_{i,S} \downarrow \min_{j \in S}\left\{f_{j,S\setminus\{j\}} + d(i, C_j)\right\}$$

其中 $\downarrow$ 表示 a=min(a,b) ，$d$ 表示图上两点的最短路径长度的函数。

这里 $d$ 因为我们只需要 $C$ 和其他点的距离，因此我们只需要 $\mathcal{O}(nk)$ 扫一下就好了

时间复杂度 $\mathcal{O}(nk + k^22^k)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define K ((int)(18))

int n,m,k,c[K],d[K][N],f[K][(1 << K)];
vector<int> vec[N];
void bfs(int p)
{
    for(int i = 1; i <= n; i++) d[p][i] = INF;
    queue<int> q; d[p][c[p]] = 0; q.push(c[p]);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(auto v : vec[u]) {
            if(d[p][v] == INF) {
                d[p][v] = d[p][u] + 1; q.push(v);
            }
        }
    }
}
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;
        down(f[i][S], dp(j, S | (1 << j)) + d[j][c[i]]);
    }
    return f[i][S];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f, -1, sizeof(f));
    cin >> n >> m;
    for(int i = 1, x,y; i <= m; i++)
    {
        cin >> x >> y;
        vec[x].push_back(y); vec[y].push_back(x);
    }
    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(d[i][c[0]] == INF) return cout << "-1\n", 0;
    int res = INF;
    for(int i = 0; i < k; i++) down(res, dp(i, 1 << i) + 1);
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] [ABC190E] Magical Ornament 题解 - Jia_ye 的学习笔记 - 洛谷博客