知识点：图论，哈密尔顿通路，状压 DP
qbxt 考试题，无链接。
扯
感觉这题挺有趣的，用到的技巧很多，所以来详细写一写。
题意简述
给定 \(n\) 个好数和 \(m\) 个坏数，以及参数 \(k\)。
好数和坏数均为 \(k\) 位数，且由 \(1\sim 4\) 组成。
求包含所有好数但不包含任何坏数，且只由 \(1\sim 4\)组成的数中，各位数字之和最小值。
保证一定有解。
\(1\le n\le 20\)，\(1\le m\le 10^4\)，\(1\le k\le 8\)。
分析题意
题目实际上要求构造一个 各位之和最小的，包含所有好数，不包含所有坏数的 \(1\sim 4\) 的数字串。
这东西长得挺字符串的，从自动机的角度想一想。
令自动机每个状态代表一个 \(k\) 位的四进制数，可以发现一些东西。
在数字串后添加一个数，即可转移到下一个状态，新状态等于原状态后 \(k+1\) 位后接上新添加的数。
问题变为构造一个各位之和最小的串，使其在自动机上匹配时，能匹配到所有好数对应的状态，且避开所有坏数对应的状态。
把自动机的思路进行抽象，发现可以转成一般图论问题做。
把 \(k\) 位的四进制数看成节点，把添加数得到的转移看成边，添加的数可以看做边权（代价为数的各位之和）。
问题变为求一条经过所有好数节点的路径，使边权之和最小。
有一个很显然的结论，最优的构造串的前 \(k\) 位，后 \(k\) 位一定是好数。
正确性显然，删去前后不是好数的部分，一定使答案更优。
则求得的路径，一定是 从好数开始，到好数结束 的。
再有 \(1\sim 4\) 组成的 \(k\) 位数最多有 65536 个，直接跑承受不住。
再考虑上述过程，我们并不关心从好数到好数的过程，我们只希望从 好数到好数 时的花费尽量少。
好数数量较少，可以以每个好数状态为起点，跑出它到其他好数的最短路，即为花费。
按上述过程处理后可以建出一张新图。
新图中 只有好数节点，好数与好数之间以上面处理出的值为边权。
显然新图是一张完全图。
显然求得的路径实际上是一条 哈密尔顿通路，因为多次经过同一个好数节点是无意义的。
问题变为求边权值之和最小的哈密尔顿通路。
发现新图中节点数量 \(\le 20\)，考虑状压 DP 求解。
设 \(f_{u,S}\) 表示最后 \(k\) 位为好数 \(u\)，好数的出现情况为 \(S\) 时的最小代价。
转移时枚举当前的最后 \(k\) 位对应的好数 \(u\)，再枚举转移后最后 \(k\) 位对应的好数 \(v\)，有：
实现上的一些技巧
好数最多有八位，直接作为数组下标显然不可，且有很多空间并没有被使用。
发现好数可以看做四进制数，考虑四进制转 10 进制，再以 10 进制作为下标即可。
在转化为完全图的哈密尔顿通路问题前的预处理中，直接跑最短路可能会 T。
发现边权值仅为 \(1\sim 4\)，考虑拆边，将 1 条边权值为 \(d\) 的边，拆成 \(d\) 条边权值为 1 的边。
设 \(dis_{u,i}\) 表示到达节点 \(u\)，还剩 \(i\) 条 1 边没有被统计答案，的最小花费。
以二元组 \((u,i)\) 作为队列中的状态，仅有 \(i=0\) 的状态能够转移到其他数字。
即可进行 bfs 求最短路，具体实现见代码。
爆零小技巧
赋 初 值
代码实现
//知识点：图论，哈密尔顿通路，状压 DP
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#define pr std::pair
#define mp std::make_pair
#define ll long long
const int kMaxn = 20 + 1;
const int kMaxm = 1e4 + 10;
const int kMaxNode = 1e5 + 10;
const int kInf = 1e9 + 2077;
//=============================================================
int n, m, k, good[kMaxn];
//dis[i][j]：令数字串最后 k 位为 i，还剩 j 个边权没有计算时的最小花费。
//将权值为 1~4 的边拆成 1 边，方便 bfs，j 表示已经计算了多少边权。
int dis[kMaxNode][4];
//min_dis[i][j]：数字串最后 k 位为 good[i]，转移到数字串最后 k 位为 good[j]，所需的最小代价（代价指数字和）。
int min_dis[kMaxn][kMaxn];
//f[u][S]：数字串最后 k 位为 good[u]，好串的出现情况为 S，所需的最小代价（代价指数字和）。
int f[kMaxn][1 << 20];
bool bad[kMaxNode];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Chkmax(int &fir_, int sec_) {
if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
if (sec_ < fir_) fir_ = sec_;
}
//Id(val_)：获得四进制数 val_ 对应的十进制数。
//如有：1111->0，1113->2，1122->5。
int Id(int val_) {
int ret = 0;
for (int i = 0; i < k; ++ i) {
//等价于：(val_%10 - 1) \times 4^{i}
ret |= ((val_ % 10 - 1) << (2 * i));
val_ /= 10;
}
return ret;
}
int Sum(int val_) {
int ret = 0;
for (int i = 1; i <= k; ++ i) {
ret += val_ % 10;
val_ /= 10;
}
return ret;
}
void Bfs(int s_) {
std :: queue <pr <int, int> > q;
memset(dis, 63, sizeof (dis)); //傻逼错误，赋错初值。
dis[s_][0] = 0;
q.push(mp(s_, 0));
while (! q.empty()) {
int u = q.front().first, cnt = q.front().second;
q.pop();
if (cnt) {
if (dis[u][cnt - 1] > kInf) {
dis[u][cnt - 1] = dis[u][cnt] + 1;
q.push(mp(u, cnt - 1));
}
continue ;
}
for (int i = 1; i <= 4; ++ i) {
//此处原数 u 为十进制数，以下操作将其看成了 4 进制进行操作。
//原数二进制分解后，每两位可看做一个四进制位，因此有了下面的位运算。
int ne = (u << 2) | (i - 1); //在原数最后添加一位 i。
int all = (1 << (2 * k)) - 1; //最大的 4 进制数
int v = ne & all; //删去原数溢出的最高位
if (dis[v][i - 1] > kInf && (! bad[v])) {
dis[v][i - 1] = dis[u][cnt] + 1;
q.push(mp(v, i - 1));
}
}
}
}
void Prepare() {
n = read(), m = read(), k = read();
for (int i = 1; i <= n; ++ i) good[i] = read();
for (int i = 1; i <= m; ++ i) {
int val = read();
bad[Id(val)] = true; //傻逼错误，没加Id()
}
for (int i = 1; i <= n; ++ i) {
Bfs(Id(good[i]));
for (int j = 1; j <= n; ++ j) {
min_dis[i][j] = dis[Id(good[j])][0];
}
}
}
//=============================================================
int main() {
Prepare();
memset(f, 63, sizeof (f));
for (int i = 1; i <= n; ++ i) f[i][1 << (i - 1)] = Sum(good[i]);
int all = (1 << n);
for (int i = 0; i < all; ++ i) {
for (int u = 1; u <= n; ++ u) { //当前数字串结尾 k 位为已出现过的，好数 good[u]。
if (! (i & (1 << (u - 1)))) continue ;
for (int v = 1; v <= n; ++ v) {
if (i & (1 << (v - 1))) continue ; //转移后数字串结尾 k 位为好数 good[v]。
Chkmin(f[v][i | (1 << (v - 1))], f[u][i] + min_dis[u][v]);
}
}
}
int ans = kInf;
for (int i = 1; i <= n; ++ i) Chkmin(ans, f[i][all - 1]);//最后 k 位为好数。
printf("%d\n", ans);
return 0;
}