Fukuoka 2011 F - City Merger <路径压缩,位运算,AC自动机>

本题求用最短的长度字符串包含所给子串...由于存在多串匹配的问题...容易联想到AC自动机...
       最多14个city..用14位的二进制数表示已经在串中否...对多串构造Trie树..进一步构造好AC自动机...可以用dp [ k ] [ i  ] [ x ] 来表示长度为k的串..末字符落在trie树的i处..包含14个关系的x...但这样的复杂度..以最坏的考虑..会有240*240*16384=943718400=9*10^8...无法接受...
     那么此时就要压缩路径了..由于Trie树中有很多无法产生更新的点...没必要dp时一次又一次的路过...所以将Trie树中x非0的点找出来...从每个点开始BFS...做出到其他有效点的最短距离...这样大大优化了dp过程...    

Program:
[cpp] 
#include<iostream> 
#include<string.h> 
#include<stdio.h> 
#include<queue> 
#include<algorithm> 
#include<stack> 
#include<math.h> 
#include<map> 
#define oo 1000000000 
using namespace std;   
struct node 
{ 
    int fail,son[26],city,w; 
}point[1001];  
struct node2 
{ 
    int len,x; 
}; 
int n,m,k,g,arc[303][303],need[303],l[303],dp[2][303][18000]; 
char s[30];  
queue<int> myqueue; 
void Built_Trie() 
{ 
       int len,i,j,k,h,x; 
       memset(point,0,sizeof(point)); 
       m=0; g=1; 
       for (k=0;k<n;k++) 
       { 
             scanf("%s",s); 
             len=strlen(s); 
             h=0; 
             for (i=0;i<len;i++) 
             { 
                    x=s[i]-'A'; 
                    if (!point[h].son[x]) point[h].son[x]=++m; 
                    h=point[h].son[x];    
             } 
             point[h].w|=g;  
             g*=2; 
       } 
       g--; 
       return; 
} 
void Built_AC_Automation() 
{ 
       int i,h,k; 
       while (!myqueue.empty()) myqueue.pop(); 
       for (i=0;i<26;i++) 
          if (point[0].son[i]) myqueue.push(point[0].son[i]);  
       while (!myqueue.empty()) 
       { 
               h=myqueue.front(); 
               myqueue.pop(); 
               point[h].w|=point[point[h].fail].w; 
               for (i=0;i<26;i++) 
               { 
                     k=point[h].fail; 
                     while (!point[k].son[i] && k) k=point[k].fail;  
                     point[point[h].son[i]].fail=point[k].son[i];   
                     if (!point[h].son[i])  
                          point[h].son[i]=point[k].son[i]; 
                      else 
                          myqueue.push(point[h].son[i]); 
               }                    
       } 
       return;        
} 
void Built_Arc() 
{ 
       int i,k,h,len[303]; 
       memset(arc,-1,sizeof(arc));  
       n=0; 
       for (k=0;k<=m;k++) 
          if (point[k].w)  
          { 
                need[n++]=k;  
                point[k].city=n; 
          } 
       need[n]=0; 
       for (k=0;k<=n;k++) 
       { 
              h=need[k]; 
              memset(len,-1,sizeof(len)); 
              myqueue.push(h); 
              len[h]=0; 
              while (!myqueue.empty()) 
              { 
                    h=myqueue.front(); 
                    myqueue.pop(); 
                    i=h; 
                    do 
                    { 
                        if (point[h].w && arc[k][point[h].city-1]==-1) 
                           arc[k][point[h].city-1]=len[h]; 
                        i=point[i].fail; 
                    }while (i); 
                    for (i=0;i<26;i++) 
                      if (len[point[h].son[i]]==-1) 
                      { 
                            len[point[h].son[i]]=len[h]+1; 
                            myqueue.push(point[h].son[i]);  
                      } 
              }  
       }      
       for (i=0;i<n;i++) l[i]=arc[n][i]; 
       return ; 
} 
int EXE_DP() 
{ 
    int p,i,j,t,k,x,ans; 
    memset(dp,-1,sizeof(dp));  
    k=0; 
    for (i=0;i<n;i++) dp[k][i][point[need[i]].w]=l[i]; 
    for (t=1;t<=n;t++) 
    { 
          k=1-k; 
          memset(dp[k],-1,sizeof(dp[k]));  
          for (i=0;i<n;i++) 
             for (j=0;j<n;j++)  
                for (p=0;p<=g;p++) 
                if (dp[1-k][j][p]!=-1) 
                { 
                       x=point[need[i]].w|p; 
                       if (dp[k][i][x]==-1 || dp[k][i][x]>dp[1-k][j][p]+arc[j][i]) 
                          dp[k][i][x]=dp[1-k][j][p]+arc[j][i]; 
                } 
    } 
    ans=oo; 
    for (i=0;i<n;i++) 
       if (dp[k][i][g]!=-1 && dp[k][i][g]<ans) ans=dp[k][i][g]; 
    return ans; 
} 
int main() 
{  
    while (~scanf("%d",&n)) 
    { 
            if (!n) break; 
            Built_Trie(); 
            Built_AC_Automation(); 
            Built_Arc();  
            printf("%d/n",EXE_DP()); 
    } 
    return 0; 
}