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

分手后的思念是犯贱 2022-08-09 14:43 11阅读 0赞

先用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,r
    
    template<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;
    }