[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;
}
参考文献: