题意：

给出n个资源串，m个病毒串，现在要如何连接资源串使得不含病毒串（可以重叠，样例就是重叠的）。

 

题解：

这题的套路和之前的很不同了，之前的AC自动机+DP的题目一般都是通过teir图去转移，

这题有点小不同，认真分析这一题，我们可以知道n个资源串，m个病毒串在AC自动机的上面是哪一个节点

所以可以根据teir图去处理出每一个资源串的节点不经过病毒串节点的最短距离，这个可以通过BFS实现。

这个一开始要处理AC自动机上的root节点，毕竟是从root节点开始走的。

处理出了每个点到其他点的最短距离之后，就变成了一个TSP问题，必须经过几个点的最短距离，状压写即可。

1 #include 
      
         2 #include 
       

Q; 82 fail[root] = root; 83 for (int i = 0; i < 2; i++) 84 if (next[root][i] == -1) next[root][i] = root; 85 else { 86 fail[next[root][i]] = root; 87 Q.push(next[root][i]); 88 } 89 while (!Q.empty()) { 90 int now = Q.front(); 91 Q.pop(); 92 if (End[fail[now]] == -1) End[now] = -1; 93 else End[now] |= End[fail[now]]; 94 for (int i = 0; i < 2; i++) 95 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 96 else { 97 fail[next[now][i]] = next[fail[now]][i]; 98 Q.push(next[now][i]); 99 }100 }101 }102 103 int mp[15][15], dis[60010], pos[15], num, dp[15][1055];104 105 void bfs(int x) {106 mem(dis, -1);107 dis[pos[x]] = 0;108 queue

q;109 q.push(pos[x]);110 while (!q.empty()) {111 int now = q.front();112 q.pop();113 for (int i = 0; i < 2; ++i) {114 int idx = next[now][i];115 if (End[idx] == -1 || dis[idx] >= 0) continue;116 dis[idx] = dis[now] + 1, q.push(idx);117 }118 }119 for (int i = 0; i < num; ++i) mp[x][i] = dis[pos[i]];120 }121 122 int solve() {123 pos[0] = 0, num = 1;124 for (int i = 0; i < cnt; ++i) if (End[i] > 0) pos[num++] = i;125 for (int i = 0; i < num; ++i) bfs(i);126 127 // for (int i = 0; i < num; ++i) {128 // for (int j = 0; j < num; ++j) {129 // printf("%d ", mp[i][j]);130 // }131 // printf("\n");132 // }133 134 135 for (int i = 0; i < num; ++i)136 for (int j = 0; j < (1 << n); ++j)137 dp[i][j] = INF;138 dp[0][0] = 0;139 for (int status = 0; status < (1 << n); ++status) {140 for (int i = 0; i < num; ++i) {141 if (dp[i][status] == INF) continue;142 for (int j = 0; j < num; ++j) {143 if (mp[i][j] == -1 || (status | End[pos[j]]) == status) continue;144 dp[j][status | End[pos[j]]] = min(dp[j][status | End[pos[j]]], dp[i][status] + mp[i][j]);145 }146 }147 }148 int ans = INF;149 for (int i = 0; i < num; ++i) ans = min(ans, dp[i][(1 << n) - 1]);150 return ans;151 }152 153 void debug() {154 for (int i = 0; i < cnt; i++) {155 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);156 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);157 printf("]\n");158 }159 }160 } ac;161 162 int main() {163 // FIN;164 while (~sffi(n, m)) {165 if (n == 0 && m == 0) break;166 ac.init();167 for (int i = 0; i < n; ++i) {168 sfs(buf);169 ac.insert(buf, (1 << i));170 }171 for (int i = 0; i < m; ++i) {172 sfs(buf);173 ac.insert(buf, -1);174 }175 ac.build();176 printf("%d\n", ac.solve());177 }178 return 0;179 }