Codeforces Round #327 (Div. 1) E. Birthday【AC自动机+网络流】

本文主要是介绍Codeforces Round #327 (Div. 1) E. Birthday【AC自动机+网络流】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先用AC自动机处理子串的问题
建立AC自动机，在上面标记出这个位置含有的串（ $num[v]$ ）以及维护fail指针含有的串（ $last[v]$ ）。
这是简单的处理，和沈阳站的B题简直异曲同工。
然后形成了一个DAG图，再用floyd算法将维护出整个DAG图。

用网络流Dinic处理最大独立集的问题，胡伯涛的论文有提及二分图的最大独立集做法。将DAG拆点转化为二分图即可。
方案直接用bfs在Dinic最大流跑完之后的残留网络上面询问，能够访问到的点就是方案。

但是这个方法是卡过去的。用匹配的方法更快！有待研究！

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<50
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define getidx(l,r) (l+r | l!=r)
#define ls getidx(l,mid)
#define rs getidx(mid+1,r)
#define lson l,mid
#define rson mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=800;
const int MAXM=10000005;struct Trie
{int next[MAXM][2], fail[MAXM], L=0, root, num[MAXM], last[MAXM];void clear(){L=0;root=newnode();}int newnode(){next[L][0]=next[L][1]=-1;num[L]=0;fail[L]=-1;last[L]=-1;L++;return L-1;}void insert(const string& s, int idx){int n=s.length(), p=root;for(int i=0; i<n; i ++){int idx=s[i]-'a';if(next[p][idx]==-1)next[p][idx]=newnode();p=next[p][idx];}num[p]=idx;}int que[MAXM];void build(){fail[root]=0;int front=0,back=0;for(int i=0; i<2; i++){if(next[root][i]==-1)next[root][i]=root;else{fail[next[root][i]]=root;que[back++]=next[root][i];}}while(front<back){int v=que[front++];if(num[fail[v]]) last[v]=fail[v];else last[v]=last[fail[v]];for(int i=0; i<2; i++){if(~next[v][i]){fail[next[v][i]]=next[fail[v]][i];que[back++]=next[v][i];}else{next[v][i]=next[fail[v]][i];}}}}
} AC;
struct edge
{int to, next, cap;edge() {}edge(int to, int next, int cap):to(to), next(next), cap(cap) {}
} e[MAXN*MAXN<<1];
int head[MAXN<<1], tot, level[MAXN<<1], preh[MAXN<<1];
void add_edge(int u, int v, int w)
{e[tot]=edge(v, head[u], w);head[u]=tot ++;e[tot]=edge(u, head[v], 0);head[v]=tot ++;
}
int que[MAXM];
int front,back;
bool bfs(int s, int t)
{memset(level, -1, sizeof level);level[s]=0;front=back=0;que[back++]=s;while(front<back){int v=que[front++];if(v==t) return true;for(int i=head[v]; ~i; i=e[i].next){int u=e[i].to;if(e[i].cap>0 && level[u]==-1){level[u]=level[v]+1;que[back++]=u;}}}return false;
}
int dfs(int v, int t, int f)
{if(v==t) return f;int w=0;for(int &i=preh[v]; ~i && f>0; i=e[i].next){int u=e[i].to;if(e[i].cap>0 && level[u] > level[v]){int d=dfs(u, t, min(f, e[i].cap));if(d>0){e[i].cap-=d;e[i^1].cap+=d;f-=d;w+=d;if(e[i].cap > 0)return w;}}}return w;
}
int max_flow(int s, int t)
{int ans=0;while(bfs(s,t)){for(int i=0; i<=t; i ++) preh[i]=head[i];ans+=dfs(s, t, INF);}return ans;
}
int pos[MAXN], fa[MAXN], N, g[MAXN][MAXN], M,  mp[MAXN], used[MAXN];
string A[MAXN];
bool cmp(int a, int b)
{if(A[a].length()==A[b].length()) return a<b;return A[a].length()<A[b].length();
}
int main()
{AC.clear();scanf("%d", &N);M=0;for(int i=1; i <= N; i ++){cin>>A[i];AC.insert(A[i], i);}AC.build();memset(head, -1, sizeof head);tot=0;memset(g, 0, sizeof g);for(int i=1; i <= N; i ++){int now=AC.root, len=A[i].length();for(int j=0; j < len; j ++){int idx=A[i][j]-'a';now=AC.next[now][idx];if(AC.num[now] > 0){g[i][AC.num[now]]=1;}if(AC.last[now] && AC.num[AC.last[now]]){g[i][AC.num[AC.last[now]]]=1;}}now=AC.fail[now];if(AC.num[now] > 0){g[i][AC.num[now]]=1;}if(AC.last[now] && AC.num[AC.last[now]]){g[i][AC.num[AC.last[now]]]=1;}}for(int k=1; k<= N; k ++){for(int i=1; i <= N; i ++){for(int j=1; j <= N; j ++){if(g[i][k] && g[k][j]) g[i][j]=1;}}}for(int i=1; i <= N; i ++){for(int j=1; j <= N; j ++){if(i != j && g[i][j]){add_edge(i, j + N, 1);}}}for(int i=1; i <= N; i ++){add_edge(0, i, 1);add_edge(i + N, N * 2 + 1, 1);}int ans=N-max_flow(0, N * 2 + 1);cout<<ans<<'\n';for(int i=1; i <= N; i ++){if(~level[i] && level[i + N]==-1){printf("%d ", i);}}printf("\n");return 0;
}