HDU 3247 Resource Archiver[AC自动机+最短路+dp]-白红宇

HDU 3247 Resource Archiver[AC自动机+最短路+dp]

阅读量：4881 次

发布时间：2019-06-11

本文共 1864 字，大约阅读时间需要 6 分钟。

题意：给n个源代码串，m个病毒串（都是01串），求最短的串，包含所有源代码串，但不包含任何病毒串，输出这个最短串的长度。

（题目没说如果不存在该输出什么，那应该就是保证一定存在吧。即没有任何一个病毒串是源代码串的子串）

思路：将所有串都加入自动机中，预处理出所有代码串之间的最短路（不经过病毒串的最短路），然后问题就变成了从trie树根节点开始，经过每个代码串结点各一次的最短路径，类似于TSP，用状压dp可解。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              using namespace std;#define rep(i,f,t) for(int i = (f), _end = (t); i <= _end; ++i)#define dep(i,f,t) for(int i = (f), _end = (t); i >= _end; --i)#define clr(c,x) memset(c,x,sizeof(c));#define debug(x) cout<<"debug "<
               
                <
                
                  0){ if(next[u][0] || next[u][1] || end[u])return -1; }else{ next[u][0] = next[u][1] = 0; } end[u] = id; return u; } void build(){ queue
                 
                   q; rep(c,0,1) if(next[0][c])q.push(next[0][c]); while(!q.empty()){ int u = q.front(); q.pop(); int fu = fail[u]; if(end[fu] == -1){ end[u] = -1; } rep(c,0,1){ int &v = next[u][c]; if(v){ q.push(v); fail[v] = next[fu][c]; }else{ v = next[fu][c]; } } } } int dt[maxs]; void bfs(int s){ clr(dt, -1); queue
                  
                    q; dt[s] = 0; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); if(u == 0 || end[u] > 0) dis[end[s]][end[u]] = dt[u]; rep(c,0,1){ int v = next[u][c]; if(end[v] < 0 || dt[v] >= 0)continue; dt[v] = dt[u] + 1; q.push(v); } } } int solve(int n){ clr(dp, INF); rep(i,1,n){ dp[1<<(i-1)][i] = dis[0][i]; } rep(S,1,(1<
                   
                    >(i-1)&1){ if(dp[S][i] == INF)while(1)puts("**"); rep(j,1,n)if( !(S>>(j-1)&1) ){ int &nxt = dp[S|(1<<(j-1))][j]; nxt = min(nxt, dp[S][i] + dis[i][j]); } } } return *min_element(dp[(1<
                    
                      0){ dis[0][i] = strlen(tmp); mp[i] = t; ++i; }else{ --n; } } rep(i,1,m){ scanf("%s",tmp); ac.insert(tmp, -1); } ac.build(); rep(i,1,n){ ac.bfs(mp[i]); } int ans = ac.solve(n); printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/DSChan/p/4861969.html

你可能感兴趣的文章