[数据结构与算法]hdu3247 Resource Archiver（AC自动机上bfs预处理+dfs/状压dp解tsp问题）

http://acm.hdu.edu.cn/showproblem.php?pid=3247

• 把所有的串挂到自动机上去，这样就能在自动机上跑最短路
• 由于最短路长度为1所以改成bfs
• 标记病毒串不能bfs经过
• 这样就变成10个串，预处理出根到每个串结尾的距离，就是先构造出哪个串
• 然后再从这个串开始跑其他串，只要状态把全部串都跑到即可（类似tsp，不过tsp最后要回来再花代价）
• 由于给了10sdfs也能接受就暴力跑了2s过

（发现自己的自动机之前的没有trie图却过了hdu板子题，甚至这道题我对拍了网上其他题解存在不同输出但是都ac了，这题数据挺水的，重在理解）

中途想了一个资源串存在公共前缀的问题，bfs中是跑出了到前缀串的距离。但是dfs的时候只是单纯判断资源串有没有跑到这个情况是可以剪枝的。因为前缀串包含在串中，因此从结果来看选择前缀串来跑更优。所以dfs的进入可以判断一下当前串是不是已经在状态中了来剪一下枝头。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=6e4+5;
const int maxm=13;
typedef int LL;
typedef pair<LL,LL>P;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL tree[maxn][2],endp[maxn],fail[maxn],pc=0;
LL num[maxn],n,m;
LL dis[maxm][maxn];
LL ans=0x3f3f3f3f;
bool vis[maxn],has[maxm];
inline void ins(string& s,LL op,LL id){
     LL cur=0;
     for(int i=0;i<s.size();i++){
        LL c=s[i]-'0';
        if(!tree[cur][c]) tree[cur][c]=++pc;
        cur=tree[cur][c];
     }
     if(1==op){
        endp[cur]|=1<<(id-1);
        num[id]=cur;
     }
     else{
        endp[cur]=-1;
     }
}
///进行bfs处理以st为起点的最短路
inline void getfail(){
    queue<LL>que;
    fail[0]=0;
    for(int i=0;i<2;i++){
        if(tree[0][i]){
            fail[i]=0;que.push(tree[0][i]);
        }
    }
    while(!que.empty()){
        LL u=que.front();que.pop();
        if(endp[fail[u]]>=0) endp[u]|=endp[fail[u]];
        for(int i=0;i<2;i++){
            if(tree[u][i]){
                fail[tree[u][i]]=tree[fail[u]][i];
                que.push(tree[u][i]);
            }
            else{
                tree[u][i]=tree[fail[u]][i];
            }
        }
    }
}
inline void bfs(LL id,LL st){
    queue<P>que;
    que.push({st,0});
    dis[id][st]=0;
    memset(vis,0,sizeof(vis));
    while(!que.empty()){
        P p=que.front();que.pop();
        LL u=p.first;LL cost=p.second;
        if(endp[u]>0){
            dis[id][u]=cost;
        }
        for(int i=0;i<2;i++){
            LL v=tree[u][i];
            if(endp[v]==-1) continue;
            if(vis[v]) continue;
            vis[v]=true;
            que.push({v,cost+1});
        }
    }
}
///节点,状态,路径和
void dfs(LL now,LL state,LL val){
     if(state==(1<<n)-1) {
        ans=min(ans,val);return;
     }
     for(int i=1;i<=n;i++){
        ///||!(1<<(i-1)&state)资源串存在公共前缀,从短的到长的更优，不会重复加
        if(!has[i]){
            has[i]=true;
            dfs(i,state|(1<<(i-1)),val+dis[now][num[i]]);
            has[i]=false;
        }
     }
}
void init(){
     ans=0x3f3f3f3f;pc=0;
     memset(tree,0,sizeof(tree));
     memset(endp,0,sizeof(endp));
     memset(fail,0,sizeof(fail));
     memset(num,0,sizeof(num));
     memset(dis,0,sizeof(dis));
     memset(has,0,sizeof(has));
}
int main(void){

    while(~scanf("%d%d", &n, &m), n+m){
        for(int i=1;i<=n;i++){
            string s;cin>>s;
            ins(s,1,i);
        }
        for(int i=1;i<=m;i++){
            string s;cin>>s;
            ins(s,0,0);
        }
        getfail();
        num[0]=0;
        for(int i=0;i<=n;i++){
            bfs(i,num[i]);
        }
        for(int i=1;i<=n;i++){
            has[i]=true;
            dfs(i,endp[num[i]],dis[0][num[i]]);
            has[i]=false;
        }
        printf("%d\n",ans);
        init();
    }
   	return 0;
}