首页 > 代码库 > hdu_3247_Resource Archiver(AC自动机+bfs+TSP)

hdu_3247_Resource Archiver(AC自动机+bfs+TSP)

2024-08-11 13:19:54   222人阅读

题目链接：hdu_3247_Resource Archiver

题意：

有n个资源串，m个病毒串，现在要将所有的资源串整合到一个串内，并且这个串不能包括病毒串，问最短的串长为多少

题解：

将资源串和病毒串都插入到AC自动机中，分别做好标记，然后用bfs求出0节点和所有资源串互相的最短距离，最后就是一个TSP的状态压缩DP。

技术分享
 1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4  5 const int AC_N=1e5+7,tyn=2; 6 struct AC_automation{ 7     int tr[AC_N][tyn],so[AC_N],v[AC_N],Q[AC_N],fail[AC_N],tot; 8     inline int getid(char x){return x-‘0‘;} 9     void nw(){so[++tot]=0,fail[tot]=0,v[tot]=0;memset(tr[tot],0,sizeof(tr[tot]));}10     void init(){tot=-1,fail[0]=-1,nw();}11     void insert(char *s,int idx,int fg,int x=0){12         for(int len=strlen(s),i=0,w;i<len;x=tr[x][w],i++)13             if(!tr[x][w=getid(s[i])])nw(),tr[x][w]=tot;14         if(fg)so[x]=1<<idx;else v[x]=1;15     }16     void build(int head=1,int tail=0){17         for(int i=0;i<tyn;i++)if(tr[0][i])Q[++tail]=tr[0][i];18         while(head<=tail)for(int x=Q[head++],i=0;i<tyn;i++)19             if(tr[x][i])fail[tr[x][i]]=tr[fail[x]][i],Q[++tail]=tr[x][i],20             so[tr[x][i]]|=so[tr[fail[x]][i]],v[tr[x][i]]+=v[tr[fail[x]][i]];21             else tr[x][i]=tr[fail[x]][i];22     }23     24 }AC;25 26 char s[AC_N];27 int path[205][205],pos[205],dp[1<<10][205],cnt,Q[AC_N],dis[AC_N],n,m;28 29 inline void up(int &a,int b){if(a>b)a=b;}30 31 void bfs(int u,int head=1,int tail=0)32 {33     memset(dis,-1,sizeof(dis));34     Q[++tail]=pos[u],dis[pos[u]]=0;35     while(head<=tail)36     {37         int now=Q[head++];38         F(i,0,1)39         {40             int q=AC.tr[now][i];41             if(dis[q]<0&&!AC.v[now])dis[q]=dis[now]+1,Q[++tail]=q;42         }43     }44     F(i,0,cnt)path[u][i]=dis[pos[i]];45 }46 47 void fuck()//TSP的dp48 {49     memset(dp,-1,sizeof(dp)),dp[0][0]=0;50     for(int i=0;i<(1<<n);i++)F(j,0,cnt)if(dp[i][j]>=0)F(k,0,cnt)if(path[j][k]>=0)51     if(dp[i|AC.so[pos[k]]][k]==-1)dp[i|AC.so[pos[k]]][k]=dp[i][j]+path[j][k];52     else up(dp[i|AC.so[pos[k]]][k],dp[i][j]+path[j][k]);53     int ans=INT_MAX;54     F(i,0,cnt)if(dp[(1<<n)-1][i]!=-1)up(ans,dp[(1<<n)-1][i]);55     printf("%d\n",ans==INT_MAX?-1:ans);56 }57 58 int main()59 {60     while(~scanf("%d%d",&n,&m)&&n+m)61     {62         AC.init(),cnt=0;63         F(i,0,n-1)scanf("%s",s),AC.insert(s,i,1);64         F(i,0,m-1)scanf("%s",s),AC.insert(s,i,0);65         AC.build();66         F(i,1,AC.tot)if(AC.so[i])pos[++cnt]=i;67         F(i,0,cnt)bfs(i);//求出0到所以资源串的距离和资源串到资源串之间的距离68         fuck();69     }70     return 0;71 }
View Code

 

hdu_3247_Resource Archiver(AC自动机+bfs+TSP)


联系
我们