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

本题求用最短的长度字符串包含所给子串...由于存在多串匹配的问题...容易联想到AC自动机...

以前做过的一道类似的题 http://blog.csdn.net/kk303/article/details/7438478

最多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:

#include<iostream>#include<string.h>#include<stdio.h>#include<queue>#include<algorithm>#include<stack>#include<math.h>#include<map>#define oo 1000000000using 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;}