yp155136 coding area

2017年12月19日星期二

(TIOJ) 1042 . E.老問題 [各種KM]

http://tioj.infor.org/problems/1042

二分圖最大權匹配算法大集合(?)

法一：Min-Cost Max-Flow

#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;

struct CostFlow {
    int n,s,t;
    static const int MAX_N = 206;
    struct Edge {
        int to,cap,rev,cost;
    };
    vector<Edge> edg[MAX_N];
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap,int cost) {
        edg[from].push_back({to,cap,SZ(edg[to]),cost});
        edg[to].push_back({from,0,SZ(edg[from])-1,-cost});
    }
    const int INF = 1e9 +7;
    int dis[MAX_N],pre[MAX_N],pre_id[MAX_N];
    bool in_que[MAX_N];
    pii flow() {
        int cost=0,flow=0;
        while (true) {
            for (int i=0;n>=i;i++) {
                dis[i] = INF;
                in_que[i] = 0;
            }
            queue<int> que;
            que.push(s);
            dis[s] = 0;
            while (!que.empty()) {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                int id=0;
                for (Edge e:edg[t]) {
                    if (e.cap >0 && dis[e.to] > dis[t] + e.cost) {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = id;
                        if (!in_que[e.to]) {
                            in_que[e.to]=1;
                            que.push(e.to);
                        }
                    }
                    id++;
                }
            }
            if (dis[t] == INF) break;
            if (dis[t] > 0) break;
            int mn_flow = INF;
            for (int i=t;i!=s;i=pre[i]) {
                mn_flow = min(mn_flow,edg[pre[i]][pre_id[i]].cap);
            }
            flow += mn_flow;
            cost += mn_flow * dis[t];
            for (int i=t;i!=s;i=pre[i]) {
                edg[pre[i]][pre_id[i]].cap -= mn_flow;
                edg[i][edg[pre[i]][pre_id[i]].rev].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} flow;

const int MAX_N = 1e2 + 6;

int a[MAX_N][MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        flow.init(2*n+2,0,2*n+1);
        for (int i=1;n>=i;i++) {
            for (int j=1;n>=j;j++) {
                scanf("%d",&a[i][j]);
                flow.add_edge(i,j+n,1,-a[i][j]);
            }
        }
        for (int i=1;n>=i;i++) {
            flow.add_edge(0,i,1,0);
        }
        for (int j=1;n>=j;j++) {
            flow.add_edge(j+n,2*n+1,1,0);
        }
        pii ret=flow.flow();
        printf("%d\n",-ret.second);
    }
}

法二：KM O(n^4)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) | rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 100 + 6;

LL a[N][N];

const LL INF = 1e15 + 7;

bool vx[N],vy[N];
LL Lx[N],Ly[N];
int match[N];

int n;

bool dfs(int i)
{
    vx[i] = 1;
    REP1(j,n)
    {
        if (!vy[j])
        {
            if (Lx[i] + Ly[j] == a[i][j])
            {
                vy[j] = 1;
                if (match[j] == -1 || dfs(match[j]))
                {
                    match[j] = i;
                    return true;
                }
            }
        }
    }
    return false;
}

int main () {
    srand(time(NULL));
    while (scanf("%d",&n) != EOF)
    {
        if (n==0) break;
        REP1(i,n)
        {
            REP1(j,n)
            {
                SL(a[i][j]);
                a[i][j] = max(a[i][j],0LL);
            }
        }
        MEM0(Lx);
        MEM0(Ly);
        REP1(i,n)
        {
            REP1(j,n)
            {
                Lx[i] = max(Lx[i],a[i][j]);
            }
        }
        MEM1(match);
        //Parr(Lx,1,n);
        //Parr(Ly,1,n);
        REP1(i,n)
        {
            //cout<<"I = "<<i<<endl;
            while (true)
            {
                MEM0(vx);
                MEM0(vy);
                if (dfs(i)) break;
                else
                {
                    LL mn = INF;
                    REP1(i,n)
                    {
                        if (!vx[i]) continue;
                        REP1(j,n)
                        {
                            if (vy[j]) continue;
                            mn = min(mn , Lx[i] + Ly[j] - a[i][j]);
                        }
                    }
                    if (mn < 0) break;
                    REP1(i,n)
                    {
                        if (vx[i]) Lx[i] -= mn;
                        if (vy[i]) Ly[i] += mn;
                    }
                }
            }
        }
        LL ans=0;
        //bool check=true;
        REP1(i,n)
        {
            if (a[ match[i] ][i] >= 0)
            {
                ans += a[ match[i] ][i];
            }
        }
        if (ans < 0) ans = 0;
        PL(ans);
    }
}

法三：KM O(n^3)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) | rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 100 + 6;

LL a[N][N];

const LL INF = 1e15 + 7;

bool vx[N],vy[N];
LL Lx[N],Ly[N];
int match[N];

int n;

LL slack_y[N];

bool dfs(int i,bool change = true)
{
    if (vx[i]) return false;
    vx[i] = 1;
    REP1(j,n)
    {
        LL val = Lx[i] + Ly[j] - a[i][j];
        if (!vy[j])
        {
            if (Lx[i] + Ly[j] == a[i][j])
            {
                vy[j] = 1;
                if (match[j] == -1 || dfs(match[j],change))
                {
                    if (change)match[j] = i;
                    return true;
                }
            }
            else
            {
                slack_y[j] = min(slack_y[j],val);
            }
        }
    }
    return false;
}

int main () {
    srand(time(NULL));
    while (scanf("%d",&n) != EOF)
    {
        if (n==0) break;
        REP1(i,n)
        {
            REP1(j,n)
            {
                SL(a[i][j]);
                a[i][j] = max(a[i][j],0LL);
            }
        }
        MEM0(Lx);
        MEM0(Ly);
        REP1(i,n)
        {
            REP1(j,n)
            {
                Lx[i] = max(Lx[i],a[i][j]);
            }
        }
        MEM1(match);
        //Parr(Lx,1,n);
        //Parr(Ly,1,n);
        REP1(i,n)
        {
            //cout<<"I = "<<i<<endl;
            REP1(i,n) slack_y[i] = INF;
            MEM0(vx);
            MEM0(vy);
            if (dfs(i)) continue;
            bool flag = true;
            while (flag)
            {
                LL mn = INF;
                REP1(j,n)
                {
                    if (!vy[j]) mn = min(mn,slack_y[j]);
                }
                REP1(i,n)
                {
                    if (vx[i]) Lx[i] -= mn;
                    if (vy[i]) Ly[i] += mn;
                    else slack_y[i] -= mn;
                }
                REP1(j,n)
                {
                    if (!vy[j] && slack_y[j] == 0)
                    {
                        vy[j] = 1;
                        if (match[j] == -1 || dfs(match[j],false))
                        {
                            flag = false;
                            break;
                        }
                    }
                }
            }
            MEM0(vx);
            MEM0(vy);
            assert(dfs(i));
        }
        LL ans=0;
        //bool check=true;
        REP1(i,n)
        {
            if (a[ match[i] ][i] >= 0)
            {
                ans += a[ match[i] ][i];
            }
        }
        if (ans < 0) ans = 0;
        PL(ans);
    }
}

2017年12月14日星期四

(IOICamp) 43. 翁山國與複利業 [Cost Flow]

https://judge.ioicamp.org/problems/43

Cost Flow (?)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int,int> pii;

struct CostFlow {
 static const int MAX_N = 2e3 + 6;
 struct Edge {
  int to,cap,rev,cost;
 };
 int s,t,n;
 vector<Edge> edg[MAX_N];
 void init(int _n,int _s,int _t) {
  n=_n;
  s=_s;
  t=_t;
  for (int i=0;n>=i;i++) {
   edg[i].clear();
  }
 }
 #define SZ(x) ((int)(x).size())
 void add_edge(int from,int to,int cap,int cost) {
  edg[from].push_back({to,cap,SZ(edg[to]),cost});
  edg[to].push_back({from,0,SZ(edg[from])-1,-cost});
 }
 static const int INF = 1e9 + 7;
 int dis[MAX_N];
 int pre[MAX_N];
 int pre_id[MAX_N];
 bool in_que[MAX_N];
 pii flow(int k) {
  int flow=0,cost=0;
  while (true) {
   for (int i=0;n>=i;i++) {
    dis[i] = INF;
    in_que[i] = false;
   }
   queue<int> que;
   que.push(s);
   dis[s] = 0;
   while (!que.empty()) {
    int t=que.front();
    que.pop();
    in_que[t] = false;
    int id=0;
    for (Edge e:edg[t]) {
     if (e.cap > 0 && dis[e.to] > dis[t] + e.cost) {
      dis[e.to] = dis[t] + e.cost;
      pre[e.to] = t;
      pre_id[e.to] = id;
      if (!in_que[e.to]) {
       que.push(e.to);
       in_que[e.to] = true;
      }
     }
     id++;
    }
   }
   if (dis[t] == INF) break;
   int mn_flow = INF;
   for (int i=t;i!=s; i=pre[i]) {
    mn_flow = min(mn_flow,edg[pre[i]][pre_id[i]].cap);
   }
   if (cost + mn_flow * dis[t] > k) break;
   flow += mn_flow;
   for (int i=t;i!=s; i=pre[i]) {
    edg[pre[i]][pre_id[i]].cap -= mn_flow;
    edg[i][edg[pre[i]][pre_id[i]].rev].cap += mn_flow;
   }
   cost += mn_flow * dis[t];
  }
  return make_pair(flow,cost);
 }
} Flow;

int main () {
 int T;
 scanf("%d",&T);
 while (T--)
    {
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        Flow.init(n,1,n);
        for (int i=1;m>=i;i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            Flow.add_edge(a,b,1,0);
            Flow.add_edge(b,a,1,c);
        }
        printf("%d\n",Flow.flow(k).first);
    }
}

(POJ) 2778. DNA Sequence [AC自動機 + 矩陣快速冪]

http://poj.org/problem?id=2778

被坑了有點久><

矩陣快速冪寫遞迴一直RE ><

#include <iostream>
#include <cstring>
#include <cassert>
#include <string>
using namespace std;

typedef long long LL;
const LL mod = 100000;

struct Matrix {
    static const int N =106;
    LL a[N][N];
    int n;
    void init(int _n)
    {
        n=_n;
        for (int i=0;n>=i;i++)
        {
            for (int j=0;n>=j;j++)
            {
                a[i][j] = 0;
            }
        }
    }
};

Matrix trans;

struct AC_Machine {
    static const int N = 106;
    static const int SIGMA = 4;
    int ch[N][SIGMA];
    int fail[N];
    int last[N];
    int val[N];
    int que[N];
    int sz,qe,qs;
    void init()
    {
        sz = 1;
        qs = qe = 0;
        memset(ch[0],0,sizeof(ch[0]));
        memset(val,0,sizeof(val));
        memset(last,0,sizeof(last));
    }
    int idx(char c)
    {
        if (c=='A') return 0;
        else if (c=='C') return 1;
        else if (c=='G') return 2;
        else if (c=='T') return 3;
        //else assert(0);
    }
    int insert(char* s,int id)
    {
        int now=0;
        int n=strlen(s);
        for (int i=0;n>i;i++)
        {
            int nxt=idx(s[i]);
            if (!ch[now][nxt])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                ch[now][nxt] = sz;
                sz++;
            }
            now = ch[now][nxt];
        }
        val[now] = id;
        return now;
    }
    void getFail()
    {
        qs = qe = 0;
        fail[0] = 0;
        for (int c=0;SIGMA >c; c++)
        {
            int nxt=ch[0][c];
            if (nxt)
            {
                fail[nxt] = 0;
                que[qe++] = nxt;
                last[nxt] = 0;
            }
        }
        while (qs != qe)
        {
            int t=que[qs++];
            for (int i=0;SIGMA>i;i++)
            {
                int nxt=ch[t][i];
                if (!nxt) continue;
                que[qe++] = nxt;
                int v=fail[t];
                while (v && !ch[v][i]) v = fail[v];
                fail[nxt] = ch[v][i];
                last[nxt] = val[ fail[nxt] ] ? fail[nxt] :last[ fail[nxt] ];
            }
        }
    }
    void AC_evolution()
    {
        qs=0;
        while (qs != qe)
        {
            int now=que[qs++];
            for (int c=0;SIGMA>c;c++)
            {
                if (!ch[now][c]) ch[now][c] = ch[fail[now] ][c];
            }
        }
    }
    void get_trans()
    {
        trans.init(sz);
        for (int i=0;sz>i;i++)
        {
            for (int j=0;SIGMA>j;j++)
            {
                int nxt=ch[i][j];
                if (!val[nxt] && !last[nxt] && !val[i] &&!last[i])
                {
                    //i --> nxt
                    trans.a[nxt][i]++;
                }
            }
        }
    }
} ac;

const int N = 12;

string s[N];
int ed[N];

Matrix operator*(const Matrix &m1,const Matrix &m2)
{
    Matrix ret;
    ret.init(m1.n);
    int n=m1.n;
    for (int i=0;n>=i;i++)
    {
        for (int j=0;n>=j;j++)
        {
            for (int k=0;n>=k;k++)
            {
                ret.a[i][j] += m1.a[i][k]*m2.a[k][j];
            }
        }
    }
    for (int i=0;n>=i;i++)
    {
        for (int j=0;n>=j;j++)
        {
            ret.a[i][j] %= mod;
        }
    }
    return ret;
}

Matrix poww(Matrix a,LL n)
{
    Matrix ret;
    ret.init(a.n);
    for (int i=0;a.n>=i;i++)
    {
        ret.a[i][i] = 1;
    }
    Matrix now = a;
    while (n)
    {
        if (n&1) ret = ret * now;
        now = now * now;
        n >>= 1;
    }
    return ret;
}

LL powww(LL a,LL n,LL mod)
{
    if (n==1) return a;
    LL ret = powww(a,n/2,mod);
    ret *= ret;
    ret %= mod;
    if (n&1) ret *= a;
    return ret%mod;
}

int main ()
{
    int m,n;
    cin >> m >> n;
    if (m==0)
    {
        cout << powww(4,n,mod) <<endl;
        return 0;
    }
    ac.init();
    for (int i=1;m>=i;i++)
    {
        char qaq[106];
        cin >> qaq;
        ed[i] = ac.insert(qaq,i);
    }
    ac.getFail();
    ac.AC_evolution();
    ac.get_trans();
    //cout<<"trans.n = "<<trans.n<<endl;
    Matrix ret=poww(trans,n);
    //cout <<"QAQ" << endl;
    LL ans=0;
    for (int i=0;trans.n>=i;i++)
    {
        if (ac.val[i] == 0 && ac.last[i] == 0)ans += ret.a[i][0];
    }
    cout << ans%mod << endl;
}

(IOICamp) 86. 秘密讀書會 [AC自動機的DP]

https://judge.ioicamp.org/problems/86

AC自動機的DP。

把AC自動機上面的點當作狀態去DP，隨時統計到達當前狀態的方法數。

注意到達 Si 的時候，要把dp設為0，因為不能到達。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,LL>  pii;
typedef pair<pii,LL> piii;
#define F first
#define S second
const LL mod = 1e9 + 7;
const int N = 106;

struct AC_Automata {
    static const int N = 2e4 + 6;
    static const int M = 106;
    static const int SIGMA = 26;
    LL dp[M][N];
    int ch[N][SIGMA];
    int val[N];
    int sz;
    int last[N],fail[N];
    int que[N],qs,qe;
    void init()
    {
        sz = 1;
        memset(ch[0],0,sizeof(ch[0]));
        qs = qe  = 0;
        memset(val,0,sizeof(val));
        memset(last,0,sizeof(last));
    }
    int idx(char c)
    {
        return c-'a';
    }
    int insert(string s,int v)
    {
        int now=0;
        int n=s.size();
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            if (!ch[now][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz] = 0;
                ch[now][c] = sz++;
            }
            now = ch[now][c];
        }
        val[now] = v;
        return now;
    }
    void print(int j)
    {
        if (j)
        {
            //now we match string v[j]
            print(last[j]);  //may match multiple strings
        }
    }
    void getFail()
    {
        qs=0,qe=0;
        fail[0]=0;
        for (int c=0;SIGMA >c;c++)
        {
            int now=ch[0][c];
            if (now)
            {
                fail[now] = 0;
                que[qe++] = now;
                last[now] = 0;
            }
        }
        while (qs != qe)
        {
            int t=que[qs++];
            for (int c=0;SIGMA > c;c++)
            {
                int now=ch[t][c];
                if (!now) continue;
                que[qe++] = now;
                int v=fail[t];
                while (v && !ch[v][c]) v=fail[v];
                fail[now] = ch[v][c];
                last[now] = val[ fail[now] ]? fail[now]:last[ fail[now] ];
            }
        }
    }
    void Find(string s)
    {
        getFail();
        //cout<<"qe = "<<qe<<endl;
        int n=s.size();
        int now=0;
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            while (now && !ch[now][c]) now = fail[now];
            now = ch[now][c];
        }
    }
    void AC_evolution()
    {
        for (qs=0;qs!=qe;)
        {
            int now=que[qs++];
            for (int i=0;SIGMA>i;i++)
            {
                if (ch[now][i] == 0) ch[now][i] = ch[fail[now]][i];
            }
        }
    }
    LL get_answer(int n)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for (int i=0;n-1>=i;i++)
        {
            for (int j=0;sz>j;j++)
            {
                for (int c=0;SIGMA>c;c++)
                {
                    int nxt = ch[j][c];
                    if (!val[nxt] && !last[nxt])
                    {
                        dp[i+1][nxt] += dp[i][j];
                        dp[i+1][nxt] %= mod;
                    }
                }
            }
        }
        LL ret =0 ;
        for (int j=0;sz>j;j++)
        {
            ret += dp[n][j];
            ret %= mod;
        }
        return ret%mod;
    }
} ac;

string s[N];
int ed[N];

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n,m;
        cin >> n >> m;
        ac.init();
        for (int i=1;m>=i;i++)
        {
            cin >> s[i];
            ed[i] = ac.insert(s[i],i);
        }
        ac.getFail();
        ac.AC_evolution();
        cout<<ac.get_answer(n)<<endl;
    }
}

(UVa) 1449 - Dominating Patterns [AC 自動機]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4195

AC自動機起飛囉~

參考處；訓練指南 + IOICAMP 2015

#include <bits/stdc++.h>
using namespace std;

struct AC_Automata {
    static const int N = 2e4 + 6;
    static const int SIGMA = 26 + 1;
    int ch[N][SIGMA];
    int val[N];
    int sz;
    int last[N],fail[N];
    int que[N],qs,qe;
    int cnt[N];
    void init()
    {
        sz = 1;
        memset(ch[0],0,sizeof(ch[0]));
        qs = qe  = 0;
        memset(cnt,0,sizeof(cnt));

        memset(cnt,0,sizeof(val));
        memset(cnt,0,sizeof(last));
}
    int idx(char c)
    {
        return c-'a';
    }
    int insert(string s,int v)
    {
        int now=0;
        int n=s.size();
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            if (!ch[now][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz] = 0;
                ch[now][c] = sz++;
            }
            now = ch[now][c];
        }
        val[now] = v;
        return now;
    }
    void print(int j)
    {
        if (j)
        {
            //now we match string v[j]
            print(last[j]);  //may match multiple strings
        }
    }
    void getFail()
    {
        qs=0,qe=0;
        fail[0]=0;
        for (int c=0;SIGMA >c;c++)
        {
            int now=ch[0][c];
            if (now)
            {
                fail[now] = 0;
                que[qe++] = now;
                last[now] = 0;
            }
        }
        while (qs != qe)
        {
            int t=que[qs++];
            for (int c=0;SIGMA > c;c++)
            {
                int now=ch[t][c];
                if (!now) continue;
                que[qe++] = now;
                int v=fail[t];
                while (v && !ch[v][c]) v=fail[v];
                fail[now] = ch[v][c];
                last[now] = val[ fail[now] ]? fail[now]:last[ fail[now] ];
            }
        }
    }
    void Find(string s)
    {
        getFail();
        //cout<<"qe = "<<qe<<endl;
        int n=s.size();
        int now=0;
        for (int i=0;n>i;i++)
        {
            int c=idx(s[i]);
            while (now && !ch[now][c]) now = fail[now];
            now = ch[now][c];
            cnt[now]++;
        }
        for (int i=qe-1;i>=0;i--)
        {
            cnt[ fail[que[i]] ] += cnt[ que[i] ];
        }
    }
    void AC_evolution()
    {
        for (qs=1;qs!=qe;)
        {
            int now=que[qs++];
            for (int i=0;SIGMA>i;i++)
            {
                if (ch[now][i] == 0) ch[now][i] = ch[fail[now]][i];
            }
        }
    }
} ac;

const int N = 156;
string s[N];
int ed[N];

int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    while (cin >> n)
    {
        if (!n) break;
        ac.init();
        for (int i=1;n>=i;i++)
        {
            cin >>s[i];
            ed[i] = ac.insert(s[i],i);
        }
        string t;
        cin >> t;
        ac.Find(t);
        int mx=0;
        for (int i=1;n>=i;i++)
        {
            mx = max(mx,ac.cnt[ ed[i] ]);
        }
        cout << mx <<endl;
        for (int i=1;n>=i;i++)
        {
            if(ac.cnt[ ed[i] ] == mx) cout << s[i] << endl;
        }
    }
}

訂閱：文章 (Atom)

2017年12月19日 星期二