正題

題目鏈接:https://www.luogu.com.cn/problem/CF590E

---

題目大意

$n$個字符串，求一個最大的集合使其中沒有任何串是其他集合內字符串的子串

---

解題思路

先用$AC$自動機建立好$fail$樹+傳遞閉包就可以確定好兩兩之間的子串關系了，之后用網絡流最大匹配求最大獨立集即可

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e7+10,M=1600,inf=2147483647/3; struct node{int to,next,w; }a[1010000]; int n,tot=1,cnt,s,t; int ch[N][2],fail[N],fa[N],cur[M]; int ls[M],ed[N],pos[N],dep[M]; bool d[M][M];char st[N]; queue<int> q; void Make(char *s,int num){int x=1,len=strlen(s);for(int i=0;i<len;i++){int w=s[i]-'a';if(!ch[x][w])ch[x][w]=++cnt,fa[cnt]=x;x=ch[x][w];}ed[x]=num;pos[num]=x; return; } void Bfs(){ch[0][0]=ch[0][1]=1;q.push(1);fail[1]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<2;i++)if(!ch[x][i])ch[x][i]=ch[fail[x]][i]; else{q.push(ch[x][i]);int y=fail[x];fail[ch[x][i]]=ch[y][i]; }}return; } void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs() {memset(dep,0,sizeof(dep));memcpy(cur,ls,sizeof(cur));while(!q.empty()) q.pop();q.push(s);dep[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!dep[y]&&a[i].w){dep[y]=dep[x]+1;q.push(y);}}}if(dep[t]) return true;return false; } int dinic(int x,int flow) {int rest=0,k;if(x==t||!flow) return flow;for(int i=cur[x];i;i=a[i].next){int y=a[i].to;cur[x]=i;if(dep[x]+1==dep[y]&&a[i].w){rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow) return flow;}}if(!rest) dep[x]=0;return rest; } int main() {scanf("%d",&n);cnt=1;for(int i=1;i<=n;i++){scanf("%s",st);Make(st,i);}Bfs();ed[1]=-1;for(int i=1;i<=n;i++){for(int j=pos[i];j!=1;j=fa[j]){int x=fail[j];while(!ed[x])x=fail[x];int y=fail[j];while(!ed[y]){int w=fail[y];fail[y]=x;y=w;}fail[j]=x;if(j!=pos[i]&&ed[j])d[i][ed[j]]=1;if(x!=1)d[i][ed[x]]=1;}}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]|=d[i][k]&d[k][j];s=0;t=2*n+1;for(int i=1;i<=n;i++)addl(s,i,1),addl(i+n,t,1);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j&&d[i][j])addl(i,j+n,1);int ans=n;while(bfs())ans-=dinic(s,inf);printf("%d\n",ans);for(int i=1;i<=n;i++)if(dep[i]&&!dep[i+n])printf("%d ",i);return 0; }

總結

以上是生活随笔為你收集整理的CF590E-Birthday【AC自动机,最大独立集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。