[备份]算法模板大集锦

一、介绍

这是一篇赶工赶出来并且随时会更新的备份文章，里面汇集了我曾学过的所有高级（也就是太长了我记不住）算法的模板。大部分直接从以前的文章里蒯过来，所以对于任意一份模板，都说不定将来再次翻阅的时候忍受不了当时的格式/命名/写法等等而进行修改。

二、目录

1、网络流Dinic算法

2、Tarjan算法

3、倍增LCA

4、AC自动机

5、主席树

6、BKDRHash

三、正文

1、网络流Dinic算法

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 #define MAXN 205
 5 #define MAXM 205
 6 #define INF 0x3f3f3f3f
 7 
 8 int m, n, u, v, f, q[MAXN * MAXN], h[MAXN], d[MAXN], o = 1, ans;
 9 
10 struct Edge {
11     int v, next, f;
12 } e[MAXM << 1];
13 
14 int min(int a, int b) {
15     return a < b ? a : b;
16 }
17 
18 void add(int u, int v, int f) {
19     o++, e[o] = (Edge) {v, h[u], f}, h[u] = o;
20 }
21 
22 bool BFS() {
23     int head = 1, tail = 2;
24     q[1] = 1, d[1] = 1;
25     while (head != tail) {
26         int o = q[head];
27         for (int x = h[o]; x; x = e[x].next) {
28             int v = e[x].v;
29             if (!d[v] && e[x].f > 0) d[v] = d[o] + 1, q[tail++] = v;
30         }
31         head++;
32     }
33     return d[n] != 0;
34 }
35 
36 int DFS(int o, int mif) {
37     int res = 0;
38     if (mif <= 0 || o == n) return mif;
39     for (int x = h[o]; x; x = e[x].next) {
40         int v = e[x].v;
41         if (d[v] == d[o] + 1) {
42             int of = DFS(v, min(mif, e[x].f));
43             e[x].f -= of, e[x ^ 1].f += of, mif -= of, res += of;
44             if (!mif) break;
45         }
46     }
47     return res;
48 }
49 
50 int main() {
51     scanf("%d %d", &m, &n);
52     for (int i = 1; i <= m; i++) scanf("%d %d %d", &u, &v, &f), add(u, v, f), add(v, u, 0);
53     while (BFS()) ans += DFS(1, INF), memset(d, 0, sizeof(d)); 
54     printf("%d", ans);
55     return 0;
56 }

2、Tarjan算法

 1 #include <cstdio>
 2 
 3 #define MAXN 500005
 4 #define MAXM 500005
 5 
 6 int n, m, u[MAXN], v[MAXN], tw[MAXN], ts, p, to, tb[MAXN], th[MAXN];
 7 int w[MAXN], b[MAXN], s, h[MAXN], o, lik[MAXN];
 8 int dfn[MAXN], low[MAXN], ins[MAXN], st[MAXN], tot, t, tim;
 9 int f[MAXN], ans;
10 
11 struct Edge {
12     int v, next;
13 } e[MAXM], te[MAXM];
14 
15 int min(int a, int b) {
16     return a < b ? a : b; 
17 }
18 
19 int max(int a, int b) {
20     return a > b ? a : b; 
21 }
22 
23 void add(int u, int v, int t) {
24     if (t) to++, te[to] = (Edge) {v, th[u]}, th[u] = to;
25     else o++, e[o] = (Edge) {v, h[u]}, h[u] = o;
26 }
27 
28 void init() {
29     scanf("%d %d", &n, &m);
30     for (int i = 1; i <= m; i++) scanf("%d %d", &u[i], &v[i]), add(u[i], v[i], 1);
31     for (int i = 1; i <= n; i++) scanf("%d", &tw[i]);
32     scanf("%d %d", &ts, &p);
33     for (int i = 1; i <= p; i++) scanf("%d", &o), tb[o] = 1;
34 }
35 
36 void tarjan(int o) {
37     dfn[o] = low[o] = ++tim, ins[o] = 1, st[++t] = o;
38     for (int x = th[o]; x; x = te[x].next) {
39         int v = te[x].v;
40         if (!dfn[v]) tarjan(v), low[o] = min(low[v], low[o]);
41         else if (ins[v] && dfn[v] < low[o]) low[o] = dfn[v];
42     }
43     if (dfn[o] == low[o]) {
44         int x; tot++;
45         do x = st[t--], ins[x] = 0, lik[x] = tot; while (x != o); 
46     }
47 }
48 
49 void rebuild() {
50     for (int i = 1; i <= m; i++) if (lik[u[i]] != lik[v[i]]) add(lik[u[i]], lik[v[i]], 0);
51     for (int i = 1; i <= n; i++) {
52         w[lik[i]] += tw[i]; 
53         if (i == ts) s = lik[i];
54         if (tb[i]) b[lik[i]] = 1;
55     }
56     f[s] = w[s];
57 }
58 
59 void DFS(int o) {
60     if (b[o]) ans = max(ans, f[o]);
61     for (int x = h[o]; x; x = e[x].next) {
62         int v = e[x].v;
63         if (f[o] + w[v] > f[v]) f[v] = f[o] + w[v], DFS(v);
64     }
65 }
66 
67 int main() {
68     init();
69     for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
70     rebuild();
71     DFS(s); 
72     printf("%d", ans);
73     return 0;
74 }

3、倍增LCA

 1 void prep() {
 2     for (int i = 1; i <= n; i++) p[i][0] = fa[i];
 3     for (int j = 1; (1 << j) <= n; j++)
 4         for (int i = 1; i <= n; i++) 
 5             if (p[i][j - 1]) p[i][j] = p[p[i][j - 1]][j - 1];
 6 }
 7 
 8 int lca_h() {
 9     if (d[x] < d[y]) swap(x, y);
10     while (d[x] != d[y]) {
11         int o = 1;
12         while (d[p[x][o]] > d[y]) o++;
13         x = p[x][o - 1];
14     }
15     while (x != y) {
16         int o = 1;
17         while (p[x][o] != p[y][o]) o++; 
18         x = p[x][o - 1], y = p[y][o - 1];
19     }
20     return x;
21 }

4、AC自动机

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 #define MAXM 1000005
 5 
 6 int T, n, tot, q[MAXM], ls, l, r;
 7 char s[55], ch[MAXM];
 8 
 9 struct Tree {
10     int a[26], x, f;
11 } t[MAXM];
12 
13 void insert() {
14     int o = r;
15     for (int i = 0; i < ls; i++) {
16         int x = s[i] - 'a';
17         if (!t[o].a[x]) t[o].a[x] = ++tot;
18         o = t[o].a[x];
19     }
20     t[o].x++;
21 }
22 
23 void getf() {
24     int head = 1, tail = 2;
25     q[1] = r;
26     while (head != tail) {
27         int o = q[head];
28         for (int i = 0; i <= 25; i++) {
29             int v = t[o].a[i];
30             if (!v) continue;
31             if (o == r) t[v].f = r;
32             else {
33                 int of = t[o].f;
34                 while (of) {
35                     if (t[of].a[i]) {
36                         t[v].f = t[of].a[i];
37                         break;
38                     }
39                     of = t[of].f;
40                 }
41                 if (!of) t[v].f = r;
42             }
43             q[tail++] = v; 
44         }
45         head++;
46     }
47 }
48 
49 int find() {
50     int ans = 0, x = r;
51     for (int i = 0; i < l; i++) {
52         int o = ch[i] - 'a';
53         while (!t[x].a[o] && x != r) x = t[x].f;
54         x = t[x].a[o] ? t[x].a[o] : r;
55         int y = x;
56         while (t[y].x) ans += t[y].x, t[y].x = 0, y = t[y].f;
57     }
58     return ans;
59 }
60 
61 int main() {
62     scanf("%d", &T);
63     for (int i = 1; i <= T; i++) {
64         scanf("%d", &n), r = ++tot;
65         for (int j = 1; j <= n; j++) scanf("%s", s), ls = strlen(s), insert();
66         getf();
67         for (int j = r + 1; j <= tot; j++) if (!t[j].f) t[j].f = r;
68         scanf("%s", ch), l = strlen(ch);
69         printf("%d
", find());
70     }
71     return 0;
72 }

5、主席树

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 #define MAXN 100005
 6 
 7 int T, n, m, l, r, k, tot, root[MAXN], b[MAXN], lik[MAXN];
 8 
 9 struct num {
10     int w, n, r;
11 } a[MAXN];
12 
13 struct cmpw {
14     bool operator () (num a, num b) {
15         return a.w < b.w;
16     }
17 } cw;
18 
19 struct cmpn {
20     bool operator () (num a, num b) {
21         return a.n < b.n;
22     }
23 } cn;
24 
25 struct Tree {
26     int l, r, w;
27 } t[MAXN * 20];
28 
29 void chg() {
30     sort(a + 1, a + n + 1, cw);
31     for (int i = 1; i <= n; i++) a[i].r = i;
32     sort(a + 1, a + n + 1, cn);
33     for (int i = 1; i <= n; i++) b[i] = a[i].r, lik[b[i]] = a[i].w;
34 }
35 
36 void build(int o, int l, int r, int w, int x) {
37     t[o] = t[x], t[o].w++;
38     if (l == r) return;
39     int m = (l + r) >> 1;
40     if (w <= m) build(t[o].l = ++tot, l, m, w, t[x].l);
41     else build(t[o].r = ++tot, m + 1, r, w, t[x].r);
42 }
43 
44 int query(int rl, int rr, int l, int r, int k) {
45     if (l == r) return l;
46     int w = t[t[rr].l].w - t[t[rl].l].w, m = (l + r) >> 1;
47     return w >= k ? query(t[rl].l, t[rr].l, l, m, k) : query(t[rl].r, t[rr].r, m + 1, r, k - w);
48 }
49 
50 int main() {
51     scanf("%d", &T);
52     for (int j = 1; j <= T; j++) {
53         root[0] = 0, tot = 0;
54         scanf("%d %d", &n, &m);
55         for (int i = 1; i <= n; i++) scanf("%d", &a[i].w), a[i].n = i;
56         chg();
57         for (int i = 1; i <= n; i++) 
58             build(root[i] = ++tot, 1, n, b[i], root[i - 1]);
59         for (int i = 1; i <= m; i++) {
60             scanf("%d %d %d", &l, &r, &k);
61             printf("%d
", lik[query(root[l - 1], root[r], 1, n, k)]);
62         }
63     }
64     return 0; 
65 }

6、BKDRHash

1 #define x 131
2 #define MOD 1000000007
3 int h[MAXN]; char a[MAXN];
4 void getHash() {
5 　　int len = strlen(a);
6 　　for (int i = 0; i <= len - 1; i++) h[i] = (h[i - 1] * x + a[i]) % MOD;
7 }