(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;
        }
    }
}

(UVa) 10600 - ACM Contest and Blackout [生成樹模板]

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

寫了個生成樹模板XDDD

#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]);
    }
}

const int N = 5e5 + 6;

bool can[N];

struct Second_MST {
    static const int N = 5e5 + 6;
    static const int P = 20; //P = lg N
    static const int INF = 1e9 + 7;
    vpii G[N];
    struct Edge {
        int a,b,c;  //cost = c
        Edge(){}
        Edge(int _a,int _b,int _c):a(_a),b(_b),c(_c){}
        bool operator<(const Edge &e1) {
            return c<e1.c;
        }
    };
    struct DisjointSet {
        int p[N];
        int sz[N];
        void init(int n) {
            for (int i=0;n>=i;i++) {
                p[i] = i;
                sz[i] = 1;
            }
        }
        int Find(int x) {
            return p[x] == x?x:p[x]=Find(p[x]);
        }
        void Union(int x,int y) {
            x=Find(x);
            y=Find(y);
            if (x==y) return;
            if (sz[x] > sz[y]) swap(x,y);
            p[x] = y;
            sz[y] += sz[x];
        }
    } djs;
    vector<Edge> edg;
    int n,m;
    int type[N]; //1 --> on original MST, 2 --> can on MST
    void init(int n,int m) {
        this->n = n;
        this->m = m;
        REP0(i,n+1)
        {
            G[i].clear();
        }
        edg.clear();
        MEM0(type);
    }
    void add_edge(int a,int b,int c) {
        edg.PB(Edge(a,b,c));
    }
    LL ret_MST;
    LL Kruskal() {
        LL ret=0;
        djs.init(n);
        sort(ALL(edg));
        int eid=-1;
        for (Edge e:edg) {
            eid++;
            if (djs.Find(e.a) == djs.Find(e.b)) {
                continue;
            }
            ret += e.c;
            djs.Union(e.a,e.b);
            G[e.a].PB({e.b,e.c});
            G[e.b].PB({e.a,e.c});
            type[eid] = 1;
        }
        this->ret_MST = ret;
        return ret;
    };
    pii lca[P][N];
    int pin[N],pout[N];
    int pid;
    void dfs(int v,int par,int cost) {
        lca[0][v] = {par,cost};
        pin[v] = pid++;
        for (pii p:G[v]) {
            if (p.F != par) dfs(p.F,v,p.S);
        }
        pout[v] = pid++;
    }
    bool is_anc(int son,int par) {
        return pin[par] <= pin[son] && pout[son] <= pout[par];
    }
    int get_path(int son,int par) {
        if (son == par) return 0;
        int ret=0;
        for (int i=P-1;i>=0;i--) {
            if (!is_anc(par,lca[i][son].F)) {
                ret = max(ret,lca[i][son].S);
                son = lca[i][son].F;
            }
        }
        return max(ret,lca[0][son].S);
    }
    int get_lca(int u,int v) {
        if (is_anc(u,v)) return v;
        if (is_anc(v,u)) return u;
        for (int i=P-1;i>=0;i--) {
            if (!is_anc(v,lca[i][u].F)) {
                u = lca[i][u].F;
            }
        }
        return lca[0][u].F;
    }
    LL get_second_MST() {
        Kruskal();
        pid=0;
        dfs(1,1,INF);
        REP1(i,P-1)
        {
            REP1(j,n)
            {
                lca[i][j] ={lca[ i-1 ][ lca[i-1][j].F ].F,max(lca[i-1][j].S, lca[ i-1 ][ lca[i-1][j].F ].S )};
            }
        }
        LL ret = ret_MST + INF;
        int eid=-1;
        for (Edge e:edg) {
            eid++;
            if (type[eid] == 1) continue;
            int lca=get_lca(e.a,e.b);
            LL mx = max(get_path(e.a,lca),get_path(e.b,lca));
            if (mx == e.c) {
                type[eid] = 2;
            }
            ret = min(ret,ret_MST - mx + e.c);
        }
        return ret;
    }
} solver;

int main () {
    int T;
    Si(T);
    while (T--) {
        int n,m;
        Sii(n,m);
        solver.init(n,m);
        REP1(i,m)
        {
            int a,b,c;
            Siii(a,b,c);
            solver.add_edge(a,b,c);
        }
        PLL(solver.Kruskal(),solver.get_second_MST());
    }
}