设为首页 加入收藏

TOP

Fukuoka 2011 F - City Merger <路径压缩,位运算,AC自动机>(一)
2015-11-21 01:05:33 来源: 作者: 【大 中 小】 浏览:8次
Tags：Fukuoka 2011 City Merger < 路径 压缩 运算 动机 >

本题求用最短的长度字符串包含所给子串...由于存在多串匹配的问题...容易联想到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?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#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 myqueue;?
void Built_Trie()?
{?
?????? int len,i,j,k,h,x;?
?????? memset(point,0,sizeof(point));?
?????? m=0; g=1;?
?????? for (k=0;k ?????? {?
???????????? scanf("%s",s);?
???????????? len=strlen(s);?
???????????? h=0;?
???????????? for (i=0;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 ?????? return ;?
}?
int EXE_DP()?
{?
??? int p,i,j,t,k,x,ans;?
??? memset(dp,-1,sizeof(dp));??
??? k=0;?
??? f
首页 上一页 1 2 下一页 尾页 1/2/2
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 3973 AC's String 下一篇：C/c++中的-->运算符

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: