[关闭]
@ljt12138 2017-04-22T01:33:54.000000Z 字数 26558 阅读 1035

[Template]省选复习计划

字符串相关

KMP算法(luogu3375)

7′40′′

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1000005, MAXM = 1005;
  5. char s1[MAXN], s2[MAXM];
  7. int pi[MAXM];
  9. void kmp_init(int len)
  10. {
  11.     pi[0] = pi[1] = 0;
  12.     int j = 0;
  13.     for (int i = 2; i <= len; i++) {
  14.         while (j && s2[j+1] != s2[i]) j = pi[j];
  15.         if (s2[j+1] == s2[i]) j++;
  16.         pi[i] = j;
  17.     }
  18. }
  20. void kmp_match(int len)
  21. {
  22.     int j = 0, p = strlen(s2+1);
  23.     for (int i = 1; i <= len; i++) {
  24.         while (j && s1[i] != s2[j+1]) j = pi[j];
  25.         if (s1[i] == s2[j+1]) ++j;
  26.         if (j == p) printf("%d\n", i-p+1), j = pi[j];
  27.     }
  28. }
  30. int main()
  31. {
  32.     scanf("%s", s1+1), scanf("%s", s2+1);
  33.     kmp_init(strlen(s2+1));
  34.     kmp_match(strlen(s1+1));
  35.     for (int i = 1, l = strlen(s2+1); i <= l; i++)
  36.         printf("%d ", pi[i]);
  37.     return 0;
  38. }

AC自动机(hdu2222)

32′42′′ 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1000005;
  5. int chl[MAXN][26], fail[MAXN], fin[MAXN], top = 0, root = 0, mak[MAXN];
  6. void push(int &nd, char *str)
  7. {
  8.     if (!nd) nd = ++top;
  9.     if (*str == '\0') fin[nd]++;
  10.     else push(chl[nd][*str-'a'], str+1);
  11. }
  13. struct node {
  14.     int to, next;
  15. } edge[MAXN];
  16. int head[MAXN], tp = 0;
  17. void push(int i, int j)
  18. { ++tp, edge[tp] = (node) {j, head[i]}, head[i] = tp; }
  20. queue<int> que;
  21. void init()
  22. {
  23.     fail[root] = 0, que.push(root);
  24.     while (!que.empty()) {
  25.         int tp = que.front(); que.pop();
  26.         for (int i = 0; i < 26; i++) {
  27.             if (!chl[tp][i]) continue;
  28.             int p = fail[tp];
  29.             while (p && !chl[p][i]) p = fail[p];
  30.             if (p) fail[chl[tp][i]] = chl[p][i];
  31.             else fail[chl[tp][i]] = root;
  32.             push(fail[chl[tp][i]], chl[tp][i]);
  33.             que.push(chl[tp][i]);
  34.         }
  35.     }
  36. }
  38. void match(int nd, char *str)
  39. {
  40.     if (fin[nd]) mak[nd] = 1;
  41.     if (*str == '\0') return;
  42.     while (nd && !chl[nd][*str-'a']) nd = fail[nd];
  43.     if (nd) match(chl[nd][*str-'a'], str+1);
  44.     else match(root, str+1);
  45. }
  47. int dp[MAXN], siz[MAXN]; // 两次collect
  48. int dfs1(int nd)
  49. {
  50.     if (!nd) return 0;
  51.     if (siz[nd] != -1) return siz[nd];
  52.     for (int i = 0; i < 26; i++)
  53.         mak[nd] |= dfs1(chl[nd][i]);
  54.     return siz[nd] = mak[nd];
  55. }
  57. int dfs2(int nd)
  58. {
  59.     if (dp[nd] != -1) return dp[nd];
  60.     dp[nd] = siz[nd];
  61.     for (int i = head[nd]; i; i = edge[i].next) {
  62.         int to = edge[i].to;
  63.         dp[nd] |= dfs2(to);
  64.     }
  65.     return dp[nd];
  66. }
  68. char str[MAXN];
  70. int T, n;
  72. void clear()
  73. {
  74.     top = root = tp = 0, memset(chl, 0, sizeof chl), memset(fail, 0, sizeof fail);
  75.     memset(fin, 0, sizeof fin), memset(mak, 0, sizeof mak);
  76.     memset(siz, -1, sizeof siz), memset(dp, -1, sizeof dp);
  77.     memset(head, 0, sizeof head);
  78. }
  80. int main()
  81. {
  82.     scanf("%d", &T);
  83.     while (T--) {
  84.         clear();
  85.         scanf("%d", &n);
  86.         for (int i = 1; i <= n; i++) {
  87.             scanf("%s", str);
  88.             push(root, str);
  89.         }
  90.         init();
  91.         scanf("%s", str);
  92.         match(root, str);
  93.         dfs1(root), dfs2(root);
  94.         int ans = 0;
  95.         for (int i = 1; i <= top; i++)
  96.             ans += dfs2(i)*fin[i];
  97.         printf("%d\n", ans);
  98.     }
  99.     return 0;
  100. }

SA

24′′04′，然而参考了模板...

第二次14′15′′

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1e5+5, N = 1e5;
  5. struct ele {
  6.     int k[2], id;
  7.     ele(){}
  8.     ele(int a, int b, int c) { k[0] = a, k[1] = b, id = c; }
  9. } RE[MAXN], RT[MAXN];
  10. int sa[MAXN], rk[MAXN], height[MAXN], sum[MAXN], n;
  11. char str[MAXN];
  13. void radix_sort()
  14. {
  15.     for (int y = 1; y >= 0; y--) {
  16.         memset(sum, 0, sizeof sum);
  17.         for (int i = 1; i <= n; i++) sum[RE[i].k[y]]++;
  18.         for (int i = 1; i <= N; i++) sum[i] += sum[i-1];
  19.         for (int i = n; i >= 1; i--) RT[sum[RE[i].k[y]]--] = RE[i];
  20.         for (int i = 1; i <= n; i++) RE[i] = RT[i];
  21.     }
  22.     for (int i = 1; i <= n; i++) {
  23.         rk[RE[i].id] = rk[RE[i-1].id];
  24.         if (RE[i].k[0] != RE[i-1].k[0] || RE[i].k[1] != RE[i-1].k[1])
  25.             rk[RE[i].id]++;
  26.     }
  27. }
  29. void calc_sa()
  30. {
  31.     for (int i = 1; i <= n; i++) RE[i] = ele(str[i]-'a'+1, 0, i);
  32.     radix_sort();
  33.     for (int k = 1; k < n; k <<= 1) {
  34.         for (int i = 1; i <= n; i++) RE[i] = ele(rk[i], i+k<=n?rk[i+k]:0, i);
  35.         radix_sort();
  36.     }
  37.     for (int i = 1; i <= n; i++) sa[rk[i]] = i;
  38. }
  40. void calc_height()
  41. {
  42.     int h = 0;
  43.     for (int i = 1; i <= n; i++) {
  44.         if (rk[i] == 1) h = 0;
  45.         else {
  46.             int k = sa[rk[i]-1];
  47.             if (--h < 0) h = 0;
  48.             while (str[i+h] == str[k+h]) h++;
  49.         }
  50.         height[rk[i]] = h;
  51.     }
  52. }
  54. int main()
  55. {
  56.     scanf("%s", str+1);
  57.     n = strlen(str+1);
  58.     calc_sa(), calc_height();
  59.     for (int i = 1; i <= n; i++) printf("%d ", sa[i]); puts("");
  60.     for (int i = 2; i <= n; i++) printf("%d ", height[i]);
  61.     return 0;
  62. }

SAM

luogu2852
8′59′′

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 40005;
  5. map<int, int> chl[MAXN];
  6. int fa[MAXN], maxl[MAXN], right_siz[MAXN];
  7. int top = 1, root = 1, last = 1;
  9. void push(int x)
  10. {
  11.     int p = last, np = ++top; maxl[np] = maxl[p]+1, right_siz[np] = 1;
  12.     while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  13.     if (!p) fa[np] = root;
  14.     else {
  15.         int q = chl[p][x];
  16.         if (maxl[q] == maxl[p] + 1) fa[np] = q;
  17.         else {
  18.             int nq = ++top; maxl[nq] = maxl[p]+1, chl[nq] = chl[q];
  19.             fa[nq] = fa[q], fa[q] = fa[np] = nq;
  20.             while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  21.         }
  22.     }
  23.     last = np;
  24. }
  26. struct node {
  27.     int to, next;
  28. } edge[MAXN];
  29. int head[MAXN], tp = 0;
  30. void push(int i, int j)
  31. { ++tp, edge[tp] = (node){j, head[i]}, head[i] = tp; }
  33. int n, k, ans = 0;
  35. void dfs(int nd)
  36. {
  37.     for (int i = head[nd]; i; i = edge[i].next) {
  38.         dfs(edge[i].to);
  39.         right_siz[nd] += right_siz[edge[i].to];
  40.     }
  41.     if (right_siz[nd] >= k) ans = max(ans, maxl[nd]);
  42. }
  44. int main()
  45. {
  46.     scanf("%d%d", &n, &k);
  47.     for (int i = 1; i <= n; i++) {
  48.         int u; scanf("%d", &u);
  49.         push(u);
  50.     }
  51.     for (int i = 2; i <= top; i++) push(fa[i], i);
  52.     dfs(root);
  53.     cout << ans << endl;
  54.     return 0;
  55. }

bzoj3238: [Ahoi2013]差异

约30′。因为longlong WA了一次。
后缀自动机parent树=逆序后缀树，后缀长度=maxl[nd]

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 500005*2;
  5. int chl[MAXN][26], fa[MAXN], maxl[MAXN];
  6. long long right_siz[MAXN];
  7. int top = 1, root = 1, last = 1;
  8. void push(int x)
  9. {
  10.     int p = last, np = ++top; maxl[np] = maxl[p]+1, right_siz[np] = 1;
  11.     while (p && !chl[p][x]) chl[p][x] = np, p = fa[p];
  12.     if (!p) fa[np] = root;
  13.     else {
  14.         int q = chl[p][x];
  15.         if (maxl[q] == maxl[p] + 1) fa[np] = q;
  16.         else {
  17.             int nq = ++top; maxl[nq] = maxl[p]+1;
  18.             memcpy(chl[nq], chl[q], sizeof chl[q]);
  19.             fa[nq] = fa[q], fa[q] = fa[np] = nq;
  20.             while (p && chl[p][x] == q) chl[p][x] = nq, p = fa[p];
  21.         }
  22.     }
  23.     last = np;
  24. }
  26. struct node {
  27.     int to, next;
  28. } edge[MAXN];
  29. int head[MAXN], tp = 0;
  30. void push(int i, int j)
  31. { edge[++tp] = (node) {j, head[i]}, head[i] = tp; }
  33. char str[MAXN];
  35. long long dfs(int nd)
  36. {
  37.     long long ans = 0, beg = right_siz[nd];
  38.     for (int i = head[nd]; i; i = edge[i].next)
  39.         ans += dfs(edge[i].to), right_siz[nd] += right_siz[edge[i].to];
  40.     for (int i = head[nd]; i; i = edge[i].next) {
  41.         int to = edge[i].to;
  42.         ans += right_siz[to]*(right_siz[nd]-right_siz[to])*maxl[nd];
  43.     }
  44.     ans += beg*(right_siz[nd]-beg)*maxl[nd];
  45.     return ans;
  46. }
  48. void init()
  49. {
  50.     scanf("%s", str+1);
  51.     int n = strlen(str+1);
  52.     for (int i = n; i >= 1; i--)
  53.         push(str[i]-'a');
  54.     for (int i = 2; i <= top; i++) push(fa[i], i);
  55.     long long ans = 0;
  56.     for (int i = 1; i <= n; i++) ans += (long long)(n-i)*(n-i+1ll)+(long long)(1ll+n-i)*(n-i)/2;
  57.     cout << ans-dfs(root) << endl;
  58. }
  60. int main()
  61. {
  62.     init();
  63.     return 0;
  64. }

树相关

树上倍增

NOIP2013 货车运输

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 10005, MAXM = 100005;
  6. struct p {
  7.     int x, y, d;
  8.     friend bool operator < (const p &a, const p &b)
  9.     { return a.d > b.d; }
  10. } edge_arr[MAXN];
  12. struct node {
  13.     int to, next, dis;
  14. } edge[MAXN];
  15. int head[MAXN], top = 0;
  16. void push(int i, int j, int k)
  17. { edge[++top] = (node){j, head[i], k}, head[i] = top; }
  18. int fa[MAXN];
  19. int findf(int nd)
  20. { return fa[nd] ? fa[nd] = findf(fa[nd]) : nd; }
  21. int n, m;
  22. int depth[MAXN], jmp[MAXN][20], min_val[MAXN][20], vis[MAXN];
  24. void dfs(int nd, int f)
  25. {
  26.     jmp[nd][0] = f, depth[nd] = depth[f] + 1;
  27.     for (int j = head[nd]; j; j = edge[j].next) {
  28.         int to = edge[j].to, d = edge[j].dis;
  29.         if (to == f) continue;
  30.         min_val[to][0] = d;
  31.         dfs(to, nd);
  32.     }
  33. }
  35. void init()
  36. {
  37.     for (int j = 1; j < 20; j++)
  38.         for (int i = 1; i <= n; i++) {
  39.             jmp[i][j] = jmp[jmp[i][j-1]][j-1];
  40.             min_val[i][j] = min(min_val[i][j-1], min_val[jmp[i][j-1]][j-1]);
  41.         }
  42. }
  44. int lca(int a, int b)
  45. {
  46.     if (depth[a] < depth[b]) swap(a, b);
  47.     for (int i = 0, d = depth[a]-depth[b]; i < 20; i++)
  48.         if ((1<<i)&d)
  49.             a = jmp[a][i];
  50.     if (a == b) return a;
  51.     for (int i = 19; i >= 0; i--)
  52.         if (jmp[a][i] != jmp[b][i])
  53.             a = jmp[a][i], b = jmp[b][i];
  54.     return jmp[a][0];
  55. }
  57. int query(int a, int b)
  58. {
  59.     int c = lca(a, b);
  60.     if (findf(a) != findf(b)) return -1;
  61.     int ans = INT_MAX;
  62.     for (int i = 0, d = depth[a]-depth[c]; i < 20; i++)
  63.         if ((1<<i)&d)
  64.             ans = min(ans, min_val[a][i]), a = jmp[a][i];
  65.     for (int i = 0, d = depth[b]-depth[c]; i < 20; i++)
  66.         if ((1<<i)&d)
  67.             ans = min(ans, min_val[b][i]), b = jmp[b][i];
  68.     return ans;
  69. }
  71. int main()
  72. {
  73.     memset(min_val, 127/3, sizeof min_val);
  74.     scanf("%d%d", &n, &m);
  75.     for (int i = 1; i <= m; i++)
  76.         scanf("%d%d%d", &edge_arr[i].x, &edge_arr[i].y, &edge_arr[i].d);
  77.     sort(edge_arr+1, edge_arr+m+1);
  78.     for (int i = 1; i <= m; i++) {
  79.         int u = edge_arr[i].x, v = edge_arr[i].y, d = edge_arr[i].d;
  80.         if (findf(u) != findf(v)) {
  81.             fa[findf(u)] = findf(v);
  82.             push(u, v, d), push(v, u, d);
  83.         }
  84.     }
  85.     depth[0] = 0;
  86.     for (int i = 1; i <= n; i++)
  87.         if (fa[i] == 0)
  88.             dfs(i, 0);
  89.     init();
  90.     int q; scanf("%d", &q);
  91.     for (int i = 1; i <= q; i++) {
  92.         int u, v; scanf("%d%d", &u, &v);
  93.         printf("%d\n", query(u, v));
  94.     }
  95.     return 0;
  96. }

树链剖分

luogu模板题
约50′

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. int lc[MAXN], rc[MAXN], l[MAXN], r[MAXN], root = 0;
  7. long long sum[MAXN], lazy[MAXN], P;
  8. int tp = 0;
  10. void build_tree(int &nd, int opl, int opr)
  11. {
  12.     nd = ++tp, l[nd] = opl, r[nd] = opr;
  13.     sum[nd] = lazy[nd] = 0;
  14.     if (opl < opr)
  15.         build_tree(lc[nd], opl, (opl+opr)/2), build_tree(rc[nd], (opl+opr)/2+1, opr);
  16. }
  17. void pdw(int nd)
  18. {
  19.     if (!lazy[nd]) return;
  20.     if (lc[nd]) lazy[lc[nd]] += lazy[nd];
  21.     if (rc[nd]) lazy[rc[nd]] += lazy[nd];
  22.     (sum[nd] += lazy[nd]*(r[nd]-l[nd]+1)) %= P;
  23.     lazy[nd] = 0;
  24. }
  25. void modify(int nd, int opl, int opr, long long dt)
  26. {
  27.     if (opl == l[nd] && opr == r[nd]) (lazy[nd] += dt) %= P;
  28.     else {
  29.         int mid = (l[nd]+r[nd])/2;
  30.         (sum[nd] += (opr-opl+1)*dt) %= P;
  31.         if (opr <= mid) modify(lc[nd], opl, opr, dt);
  32.         else if (opl >= mid+1) modify(rc[nd], opl, opr, dt);
  33.         else modify(lc[nd], opl, mid, dt), modify(rc[nd], mid+1, opr, dt);
  34.     }
  35. }
  36. long long query(int nd, int opl, int opr)
  37. {
  38.     if (nd) pdw(nd);
  39.     if (opl == l[nd] && opr == r[nd]) return sum[nd]%P;
  40.     else {
  41.         int mid = (l[nd]+r[nd])/2;
  42.         if (opr <= mid) return query(lc[nd], opl, opr);
  43.         else if (opl >= mid+1) return query(rc[nd], opl, opr);
  44.         else return (query(lc[nd], opl, mid)+query(rc[nd], mid+1, opr))%P;
  45.     }
  46. }
  48. struct node {
  49.     int to, next;
  50. } edge[MAXN*2];
  51. int head[MAXN], top = 0;
  52. void push(int i, int j)
  53. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  54. int n, m, rt;
  55. int siz[MAXN], id[MAXN], out[MAXN], ind[MAXN], rk[MAXN], depth[MAXN];
  56. int id_in_ds = 0;
  57. int fa[MAXN][21];
  59. void dfs(int nd, int f)
  60. {
  61.     fa[nd][0] = f, siz[nd] = 1, depth[nd] = depth[f] + 1;
  62.     for (int i = head[nd]; i; i = edge[i].next) {
  63.         int to = edge[i].to;
  64.         if (to == f) continue;
  65.         dfs(to, nd), siz[nd] += siz[to];
  66.     }
  67. }
  69. void dfs2(int nd, int from)
  70. {
  71.     id[nd] = ++id_in_ds, ind[nd] = from;
  72.     modify(root, id[nd], id[nd], rk[nd]);
  73.     int hev = 0;
  74.     for (int i = head[nd]; i; i = edge[i].next) {
  75.         int to = edge[i].to;
  76.         if (depth[to] < depth[nd]) continue;
  77.         if (siz[to] > siz[hev]) hev = to;
  78.     }
  79.     if (!hev) { out[nd] = id_in_ds; return; }
  80.     dfs2(hev, from);
  81.     for (int i = head[nd]; i; i = edge[i].next) {
  82.         int to = edge[i].to;
  83.         if (depth[to] < depth[nd]) continue;
  84.         if (to != hev) dfs2(to, to);
  85.     }
  86.     out[nd] = id_in_ds;
  87. }
  89. void init()
  90. {
  91.     for (int j = 1; j <= 20; j++)
  92.         for (int i = 1; i <= n; i++)
  93.             fa[i][j] = fa[fa[i][j-1]][j-1];
  94. }
  96. int lca(int a, int b)
  97. {
  98.     if (depth[a] < depth[b]) swap(a, b);
  99.     for (int d = depth[a]-depth[b], i = 0; i <= 20; i++)
  100.         if (d&(1<<i))
  101.             a = fa[a][i];
  102.     if (a == b) return a;
  103.     for (int i = 20; i >= 0; i--)
  104.         if (fa[a][i] != fa[b][i])
  105.             a = fa[a][i], b = fa[b][i];
  106.     return fa[a][0];
  107. }
  109. void add_path(int a, long long dt) // a到根
  110. {
  111.     while (a) {
  112.         modify(root, id[ind[a]], id[a], dt);
  113.         a = fa[ind[a]][0];
  114.     }
  115. }
  117. void add_son(int a, int dt)
  118. { modify(root, id[a], out[a], dt); }
  120. long long query_path(int a) //
  121. {
  122.     long long ans = 0;
  123.     while (a) {
  124.         (ans += query(root, id[ind[a]], id[a])) %= P;
  125.         a = fa[ind[a]][0];
  126.     }
  127.     return ans;
  128. }
  130. long long query_son(int a)
  131. { return query(root, id[a], out[a]); }
  133. int main()
  134. {
  135.     scanf("%d%d%d%lld", &n, &m, &rt, &P);
  136.     for (int i = 1; i <= n; i++) scanf("%d", &rk[i]);
  137.     build_tree(root, 1, n);
  138.     for (int i = 1; i < n; i++) {
  139.         int u, v; scanf("%d%d", &u, &v);
  140.         push(u, v), push(v, u);
  141.     }
  142.     depth[rt] = 0, dfs(rt, 0);
  143.     dfs2(rt, rt);
  144.     init();
  145.     for (int i = 1; i <= m; i++) {
  146.         int tp, x, y;
  147.         long long z;
  148.         scanf("%d", &tp);
  149.         if (tp == 1) {
  150.             scanf("%d%d%lld", &x, &y, &z);
  151.             int c = lca(x, y);
  152.             add_path(x, z), add_path(y, z);
  153.             add_path(c, -2*z);
  154.             modify(root, id[c], id[c], z);
  155.         } else if (tp == 2) {
  156.             scanf("%d%d", &x, &y);
  157.             int c = lca(x, y);
  158.             printf("%lld\n", ((query_path(x)+query_path(y)-2*query_path(c)+query(root, id[c], id[c]))%P+P)%P);
  159.         } else if (tp == 3) {
  160.             scanf("%d%lld", &x, &z);
  161.             add_son(x, z);
  162.         } else if (tp == 4) {
  163.             scanf("%d", &x);
  164.             printf("%lld\n", query_son(x));
  165.         } else throw;
  166.     }
  167.     return 0;
  168. }

dfs序

bzoj4034: [HAOI2015]树上操作
这个题其实树剖很好写，不过dfs序的思路太神辣所以必须发...http://www.cnblogs.com/liyinggang/p/5965981.html

pdw写错+10086...
虽然dfs序理论复杂度O(nlgn)但是由于写法太渣跑的还没有链剖快...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005*8;
  5. int n, m;
  7. int lc[MAXN], rc[MAXN], l[MAXN], r[MAXN];
  8. long long sum[MAXN], lazy[MAXN];
  9. long long num[MAXN], num_tmp[MAXN];
  10. int root = 0, top_ds = 0;
  11. void build(int &nd, int opl, int opr)
  12. {
  13.     nd = ++top_ds, sum[nd] = 0;
  14.     l[nd] = opl, r[nd] = opr;
  15.     if (opl < opr) {
  16.         build(lc[nd], opl, (opl+opr)/2);
  17.         build(rc[nd], (opl+opr)/2+1, opr);
  18.         num[nd] = num[lc[nd]] + num[rc[nd]];
  19.     } else num[nd] = num_tmp[opl];
  20. }
  22. void pdw(int nd)
  23. {
  24.     if (!lazy[nd]) return;
  25.     sum[nd] += num[nd]*lazy[nd];
  26.     if (lc[nd]) lazy[lc[nd]] += lazy[nd];
  27.     if (rc[nd]) lazy[rc[nd]] += lazy[nd];
  28.     lazy[nd] = 0;
  29. }
  31. void modify(int nd, int opl, int opr, long long dat)
  32. {
  33.     if (opl == l[nd] && opr == r[nd]) lazy[nd] += dat, pdw(nd);
  34.     else {
  35.         pdw(nd);
  36.         int mid = (l[nd]+r[nd])>>1;
  37.         if (opr <= mid) modify(lc[nd], opl, opr, dat);
  38.         else if (opl >= mid+1) modify(rc[nd], opl, opr, dat);
  39.         else modify(lc[nd], opl, mid, dat), modify(rc[nd], mid+1, opr, dat);
  40.         pdw(lc[nd]), pdw(rc[nd]);
  41.         sum[nd] = sum[lc[nd]] + sum[rc[nd]];
  42.     }
  43. }
  45. void display(int nd, int tab)
  46. {
  47.     if (!nd) return;
  48.     for (int i = 1; i <= tab; i++) putchar(' ');
  49.     printf("[%d,%d] --> sum = %lld, lazy = %lld, num = %lld\n", l[nd], r[nd], sum[nd], lazy[nd], num[nd]);
  50.     display(lc[nd], tab+2);
  51.     display(rc[nd], tab+2);
  52. }
  54. long long query(int nd, int opl, int opr)
  55. {
  56.     pdw(nd);
  57.     if (opl == l[nd] && opr == r[nd]) return sum[nd];
  58.     else {
  59.         int mid = (l[nd]+r[nd])>>1;
  60.         if (opr <= mid) return query(lc[nd], opl, opr);
  61.         else if (opl >= mid+1) return query(rc[nd], opl, opr);
  62.         else return query(lc[nd], opl, mid)+query(rc[nd], mid+1, opr);
  63.     }
  64. }
  66. struct node {
  67.     int to, next;
  68. } edge[MAXN];
  69. int head[MAXN], top = 0;
  70. void push(int i, int j)
  71. { edge[++top] = (node) {j, head[i]}, head[i] = top; }
  72. int in[MAXN], out[MAXN], ds_top = 0;
  73. int rk[MAXN];
  74. void dfs(int nd, int f)
  75. {
  76.     in[nd] = ++ds_top; num_tmp[in[nd]] = 1;
  77.     for (int i = head[nd]; i; i = edge[i].next) {
  78.         int to = edge[i].to;
  79.         if (to == f) continue;
  80.         dfs(to, nd);
  81.     }
  82.     out[nd] = ++ds_top; num_tmp[out[nd]] = -1;
  83. }
  85. void modify_point(int nd, long long dt)
  86. {
  87.     modify(root, in[nd], in[nd], dt);
  88.     modify(root, out[nd], out[nd], dt);
  89. }
  91. void modify_tree(int nd, long long dt)
  92. { modify(root, in[nd], out[nd], dt); }
  94. long long query_path(int nd)
  95. { return query(root, in[1], in[nd]); }
  97. int main()
  98. {
  99.     scanf("%d%d", &n, &m);
  100.     for (int i = 1; i <= n; i++) scanf("%d", &rk[i]);
  101.     for (int i = 1; i < n; i++) {
  102.         int u, v; scanf("%d%d", &u, &v);
  103.         push(u, v), push(v, u);
  104.     }
  105.     dfs(1, 0);
  106.     build(root, 1, 2*n);
  107.     for (int i = 1; i <= n; i++) {
  108.         modify_point(i, rk[i]);
  109.     }
  110.     for (int i = 1; i <= m; i++) {
  111.         int tp, a;
  112.         long long b;
  113.         scanf("%d", &tp);
  114.         if (tp == 1) {
  115.             scanf("%d%lld", &a, &b);
  116.             modify_point(a, b);
  117.         } else if (tp == 2) {
  118.             scanf("%d%lld", &a, &b);
  119.             modify_tree(a, b);
  120.         } else {
  121.             scanf("%d", &a);
  122.             printf("%lld\n", query_path(a));
  123.         }
  124.     }
  125.     return 0;
  126. }

lct

bzoj3832 Tree
http://hzwer.com/4422.html

约1.5h，脑残原因：zig的时候先修改了p的fa，才判断is_rt(p)...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 500005;
  6. int chl[MAXN][2], fa[MAXN], dat[MAXN], sum[MAXN], top = 0;
  7. int rev[MAXN], stk[MAXN], stop = 0, n, m;
  9. bool is_rt(int nd)
  10. { return chl[fa[nd]][0] != nd && chl[fa[nd]][1] != nd; }
  12. void pdw(int nd)
  13. {
  14.     if (!rev[nd]) return;
  15.     int &lc = chl[nd][0], &rc = chl[nd][1];
  16.     if (lc) rev[lc] ^= 1;
  17.     if (rc) rev[rc] ^= 1;
  18.     swap(lc, rc), rev[nd] = 0;
  19. }
  21. inline void update(int nd)
  22. {
  23.     sum[nd] = dat[nd]^sum[chl[nd][0]]^sum[chl[nd][1]];
  24. }
  26. void zig(int nd)
  27. {
  28.     int p = fa[nd], g = fa[p];
  29.     int tp = chl[p][0] != nd, tg = chl[g][0] != p;
  30.     int son = chl[nd][tp^1];
  31.     if (!is_rt(p)) chl[g][tg] = nd;
  32.     fa[son] = p, fa[p] = nd, fa[nd] = g;
  33.     chl[nd][tp^1] = p, chl[p][tp] = son;
  34.     update(p), update(nd);
  35. }
  37. void splay(int nd)
  38. {
  39.     stk[stop = 1] = nd;
  40.     for (int i = nd; !is_rt(i); i = fa[i]) stk[++stop] = fa[i];
  41.     while (stop) pdw(stk[stop--]);
  42.     while (!is_rt(nd)) {
  43.         int p = fa[nd], g = fa[p], tp = chl[p][0] != nd, tg = chl[g][0] != p;
  44.         if (is_rt(p)) { zig(nd); break; }
  45.         else if (tp == tg) zig(p), zig(nd);
  46.         else zig(nd), zig(nd);
  47.     }
  48. }
  50. void access(int x)
  51. {
  52.     for (int y = 0; x; x = fa[y = x])
  53.         splay(x), chl[x][1] = y, update(x);
  54. }
  56. void make_rt(int x)
  57. {
  58.     access(x), splay(x);
  59.     rev[x] ^= 1;
  60. }
  62. int find_fa(int x)
  63. {
  64.     access(x), splay(x);
  65.     while (chl[x][0]) {
  66.         if (x == chl[x][0]) throw;
  67.         x = chl[x][0];
  68.     }
  69.     return x;
  70. }
  72. void link(int x, int y)
  73. {
  74.     if (find_fa(x) == find_fa(y)) return;
  75.     make_rt(x), fa[x] = y;
  76.     access(x);
  77. }
  79. void cut(int x, int y)
  80. {
  81.     if (find_fa(x) != find_fa(y)) return;
  82.     make_rt(x);
  83.     access(y), splay(y);
  84.     if (chl[y][0] == x) chl[y][0] = 0, fa[x] = 0;
  85. }
  87. int query(int x, int y)
  88. {
  89.     make_rt(x), access(y), splay(y);
  90.     if (find_fa(y) != x) return -1;
  91.     return sum[y];
  92. }
  94. void change(int x, int dt)
  95. {
  96.     make_rt(x), splay(x), dat[x] = dt, update(x);
  97. }
  99. int main()
  100. {
  101.     scanf("%d%d", &n, &m);
  102.     for (int i = 1; i <= n; i++) scanf("%d", &dat[i]), update(i);
  103.     for (int i = 1; i <= m; i++) {
  104.         int tp, x, y;
  105.         scanf("%d%d%d", &tp, &x, &y);
  106.         if (tp == 0)
  107.             printf("%d\n", query(x, y));
  108.         else if (tp == 1)
  109.             link(x, y);
  110.         else if (tp == 2)
  111.             cut(x, y);
  112.         else change(x, y);
  113.     }
  114.     return 0;
  115. }

bzoj2843: 极地旅行社

Description

不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服
务。当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。Mirko的旅行社遭受一次
重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。Mirko希望
开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。这些冰岛从1到N标号。一开始时这些
岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0
, 1000]之间。你的程序需要处理以下三种命令：

1."bridge A B"——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于经费限制，这项命令被接受，当且仅当
A与B不联通。若这项命令被接受，你的程序需要输出"yes"，之
后会建造这座大桥。否则，你的程序需要输出"no"。
2."penguins A X"——根据可靠消息，岛屿A此时的帝企鹅数量变为X。这项命令只是用来提供信息的，你的程序不
需要回应。
3."excursion A B"——一个旅行团希望从A出发到B。若A与B连通，你的程序需要输出这个旅行团一路上所能看到的
帝企鹅数量（包括起点A与终点B），若不联通，你的程序需要输出"impossible"。

Input

第一行一个正整数N，表示冰岛的数量。
第二行N个范围[0,1000]的整数，为每座岛屿初始的帝企鹅数量。
第三行一个正整数M，表示命令的数量。接下来M行即命令，为题目描述所示。
1<=N<=30000,1<=M<=100000

16′04′′

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 30005;
  5. int chl[MAXN][2], fa[MAXN], rev[MAXN], stk[MAXN], sum[MAXN], dat[MAXN], top = 0;
  6. inline bool is_rt(int nd)
  7. { return chl[fa[nd]][0] != nd && chl[fa[nd]][1] != nd; }
  8. inline void update(int nd)
  9. { sum[nd] = sum[chl[nd][0]]+sum[chl[nd][1]]+dat[nd]; }
  11. void pdw(int nd)
  12. {
  13.     if (!rev[nd]) return;
  14.     int &lc = chl[nd][0], &rc = chl[nd][1];
  15.     if (lc) rev[lc] ^= 1;
  16.     if (rc) rev[rc] ^= 1;
  17.     swap(lc, rc), rev[nd] = 0;
  18. }
  20. void zig(int nd)
  21. {
  22.     int p = fa[nd], g = fa[p];
  23.     int tp = chl[p][0] != nd, tg = chl[g][0] != p, son = chl[nd][tp^1];
  24.     if (son) fa[son] = p;
  25.     if (!is_rt(p)) chl[g][tg] = nd;
  26.     fa[p] = nd, fa[nd] = g;
  27.     chl[nd][tp^1] = p, chl[p][tp] = son;
  28.     update(p), update(nd);
  29. }
  30. void splay(int nd)
  31. {
  32.     stk[top = 1] = nd;
  33.     for (int i = nd; !is_rt(i); i = fa[i]) stk[++top] = fa[i];
  34.     while (top) pdw(stk[top--]);
  35.     while (!is_rt(nd)) {
  36.         int p = fa[nd], g = fa[p];
  37.         int tp = chl[p][0] != nd, tg = chl[g][0] != p;
  38.         if (is_rt(p)) {zig(nd); break; }
  39.         else if (tp == tg) zig(p), zig(nd);
  40.         else zig(nd), zig(nd);
  41.     }
  42. }
  43. void access(int x)
  44. {
  45.     for (int y = 0; x; x = fa[y = x])
  46.         splay(x), chl[x][1] = y, update(x);
  47. }
  48. void make_rt(int x)
  49. { access(x), splay(x), rev[x] ^= 1; }
  50. int find(int x)
  51. {
  52.     access(x), splay(x);
  53.     while (chl[x][0]) x = chl[x][0];
  54.     return x;
  55. }
  56. void link(int x, int y)
  57. {
  58.     if (find(x) == find(y)) return;
  59.     make_rt(x), access(x), splay(x);
  60.     fa[x] = y;
  61. }
  62. void change(int x, int dt)
  63. { make_rt(x), splay(x), dat[x] = dt, update(x); }
  64. int query(int x, int y)
  65. { return make_rt(x), access(y), splay(y), sum[y]; }
  67. int n, m;
  68. char str[20];
  69. int main()
  70. {
  71.     scanf("%d", &n);
  72.     for (int i = 1; i <= n; i++) scanf("%d",&dat[i]), update(i);
  73.     scanf("%d", &m);
  74.     for (int i = 1; i <= m; i++) {
  75.         int x, y;
  76.         scanf("%s %d %d", str, &x, &y);
  77.         if (str[0] == 'e') {
  78.             if (find(x) != find(y)) puts("impossible");
  79.             else printf("%d\n", query(x, y));
  80.         } else if (str[0] == 'p') {
  81.             change(x, y);
  82.         } else if (str[0] == 'b') {
  83.             if (find(x) == find(y)) puts("no");
  84.             else
  85.                 puts("yes"), link(x, y);
  86.         }
  87.     }
  88.     return 0;
  89. }

数据结构

splay

bzoj1269: [AHOI2006]文本编辑器editor
被pdw支配的恐惧...
几个小操作的先后顺序一定要小心小心再小心啊...这次由于先检查siz后pushdown导致1h+调试...
约2h

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1024*1024*4;
  5. int chl[MAXN][2], fa[MAXN], dat[MAXN], siz[MAXN], rev[MAXN];
  6. int top = 0, root = 0;
  7. inline void update(int nd)
  8. { if(!nd) return; siz[nd] = siz[chl[nd][0]]+siz[chl[nd][1]]+1; }
  10. int stk[MAXN], skp = 0;
  12. void pdw(int nd)
  13. {
  14.     if (!rev[nd]) return;
  15.     int &lc = chl[nd][0], &rc = chl[nd][1];
  16.     rev[lc] ^= (lc != 0), rev[rc] ^= (rc != 0);
  17.     swap(lc, rc), rev[nd] = 0;
  18. }
  20. void zig(int nd)
  21. {
  22.     pdw(nd);
  23.     int p = fa[nd], g = fa[p];
  24.     int tp = chl[p][0] != nd, tg = chl[g][0] != p, son = chl[nd][tp^1];
  25.     if (g) chl[g][tg] = nd; else root = nd;
  26.     if (son) fa[son] = p;
  27.     chl[nd][tp^1] = p, chl[p][tp] = son;
  28.     fa[p] = nd, fa[nd] = g;
  29.     update(p), update(nd);
  30. }
  32. void splay(int nd, int tar = 0)
  33. {
  34.     stk[skp = 1] = nd;
  35.     for (int i = nd; fa[i]; i = fa[i]) stk[++skp] = fa[i];
  36.     while (skp) pdw(stk[skp--]);
  37.     while (fa[nd] != tar) {
  38.         int p = fa[nd], g = fa[p];
  39.         int tp = chl[p][0] != nd, tg = chl[g][0] != p;
  40.         if (g == tar) {zig(nd); break; }
  41.         else if (tp == tg) zig(p), zig(nd);
  42.         else zig(nd), zig(nd);
  43.     }
  44. }
  46. void dfs(int nd, int key)
  47. {
  48.     if (!nd) return;
  49.     // pdw(nd);
  50.     // for (int i = 1; i <= tab; i++) putchar(' ');
  51.     printf("nd = %d, lc = %d, rc = %d, dat = %c, fa = %d-- siz = %d, rev = %d\n", nd, chl[nd][0], chl[nd][1], dat[nd], fa[nd], siz[nd], rev[nd]);
  52.     dfs(chl[nd][0], key);
  53.     // putchar(dat[nd]); if (key == nd) putchar('|');
  54.     dfs(chl[nd][1], key);
  55. }
  56. int kth(int k)
  57. {
  58.     int nd = root;
  59.     while (pdw(nd), siz[chl[nd][0]] != k) {
  60.         nd = siz[chl[nd][0]] > k ? chl[nd][0] : (k -= siz[chl[nd][0]]+1, chl[nd][1]);
  61.     }
  62.     return nd;
  63. }
  65. int rk(int nd)
  66. {
  67.     splay(nd);
  68.     return siz[chl[nd][0]];
  69. }
  71. int go_prev(int nd)
  72. { return kth(rk(nd)-1); }
  73. int go_next(int nd)
  74. { return kth(rk(nd)+1); }
  75. void print(int nd)
  76. { putchar(dat[go_next(nd)]); puts(""); }
  78. int insert(int nd, int x)
  79. {
  80.     int nx = go_next(nd);
  81.     splay(nd);
  82.     splay(nx, root);
  83.     pdw(root), pdw(nx);
  84.     chl[nx][0] = ++top, fa[top] = nx, dat[top] = x, update(top), update(nx), update(nd);
  85.     return top;
  86. }
  87. void del(int nd, int len)
  88. {
  89.     int l = nd, r = kth(rk(nd)+len+1);
  90.     splay(l), splay(r, root);
  91.     pdw(l), pdw(r);
  92.     chl[r][0] = 0, update(r), update(l);
  93. }
  94. int reverse(int nd, int len)
  95. {
  96.     int l = nd, r = kth(rk(nd)+len+1), k = rk(nd);
  97.     splay(l), splay(r, root);
  98.     pdw(l), pdw(r);
  99.     rev[chl[r][0]] ^= 1;
  100.     return kth(k);
  101. }
  102. int n, k;
  103. char str[20], s[MAXN];
  105. void get_str(char str[])
  106. {
  107.     int k = -1, c;
  108.     do c = getchar(); while(c < 32 || c > 126);
  109.     while (c >= 32 && c <= 126) {
  110.         str[++k] = c;
  111.         c = getchar();
  112.     }
  113.     str[++k] = '\0';
  114. }
  115. int main()
  116. {
  117.     root = ++top, dat[top] = 0, chl[root][1] = ++top, dat[top] = 1;
  118.     fa[top] = top-1;
  119.     update(top), update(top-1);
  120.     scanf("%d", &n);
  121.     int nd = top-1;
  122.     for (int i = 1; i <= n; i++) {
  123.         scanf("%s", str);
  124.         switch(str[0]) {
  125.             case 'M': scanf("%d", &k); nd = kth(k); break;
  126.             case 'I':
  127.                 scanf("%d", &k);
  128.                 get_str(s);
  129.                 for (int i = 0, x = nd; i < k; i++)
  130.                     x = insert(x, s[i]);
  131.             break;
  132.             case 'D': scanf("%d", &k), del(nd, k); break;
  133.             case 'R': scanf("%d", &k), nd = reverse(nd, k); break;
  134.             case 'G': print(nd); break;
  135.             case 'P': nd = go_prev(nd); break;
  136.             case 'N': nd = go_next(nd); break;
  137.         }
  138.     }
  139.     return 0;
  140. }

线段树

主席树

无修改区间k大。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005, lgn = 21;
  6. int lc[MAXN*lgn], rc[MAXN*lgn], l[MAXN*lgn], r[MAXN*lgn], sum[MAXN*lgn];
  7. int root[MAXN], top = 0;
  8. int n, m;
  10. void build(int &nd, int opl, int opr)
  11. {
  12.     nd = ++top;
  13.     l[nd] = opl, r[nd] = opr, sum[nd] = 0;
  14.     if (opl < opr) 
  15.         build(lc[nd], opl, (opl+opr)/2), build(rc[nd], (opl+opr)/2+1, opr);
  16. }
  18. void push(int prev, int &nd, int pos)
  19. {
  20.     nd = ++top;
  21.     l[nd] = l[prev], r[nd] = r[prev];
  22.     if (l[prev] == r[prev]) sum[nd] = sum[prev]+1;
  23.     else {
  24.         int mid = (l[prev]+r[prev])/2;
  25.         if (pos <= mid) push(lc[prev], lc[nd], pos), rc[nd] = rc[prev];
  26.         else push(rc[prev], rc[nd], pos), lc[nd] = lc[prev];
  27.         sum[nd] = sum[lc[nd]]+sum[rc[nd]];
  28.     }
  29. }
  31. void dfs(int nd, int tab = 0)
  32. {
  33.     if (!nd) return;
  34.     for (int i = 1; i <= tab; i++) putchar(' ');    
  35.     printf("[%d,%d] -- sum = %d\n", l[nd], r[nd], sum[nd]);
  36.     dfs(lc[nd], tab+2), dfs(rc[nd], tab+2);
  37. }
  39. int query(int opl, int opr, int k)
  40. {
  41.     int i = 1, j = n, mid;
  42.     int a = root[opl-1], b = root[opr];
  43.     k--;
  44.     while (i < j) {
  45.         mid = (i+j)>>1;
  46.         if (sum[lc[b]]-sum[lc[a]] <= k) k -= sum[lc[b]]-sum[lc[a]], i = mid+1, a = rc[a], b = rc[b];
  47.         else j = mid, a = lc[a], b = lc[b];
  48.     }
  49.     return i;
  50. }
  52. int d[MAXN];
  53. int dx[MAXN];
  55. void dx_init()
  56. {
  57.     memcpy(dx, d, sizeof d);
  58.     sort(dx+1, dx+n+1);
  59. }
  61. int dx_num(int nd)
  62. { return lower_bound(dx+1, dx+n+1, nd)-dx; }
  64. int main()
  65. {
  66.     scanf("%d%d", &n, &m);
  67.     build(root[0], 1, n);
  68.     for (int i = 1; i <= n; i++) 
  69.         scanf("%d", &d[i]);
  70.     dx_init();
  71.     for (int i = 1; i <= n; i++) {
  72.         push(root[i-1], root[i], dx_num(d[i]));
  73.     }
  74.     for (int i = 1; i <= m; i++) {
  75.         int u, v, k;
  76.         scanf("%d%d%d", &u, &v, &k);
  77.         cout << dx[query(u, v, k)] << endl; 
  78.     }
  79.     return 0;
  80. }

其他

FFT

大爷题解：http://www.cnblogs.com/iiyiyi/p/5717520.html

好像把一道好题变成练模板了..之后补分析吧..

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 300005;
  5. int rev[MAXN], n;
  6. typedef complex<double> Complex;
  7. Complex A[MAXN];
  8. const double PI = acos(-1);
  9. void fft(Complex a[], int n, int flag)
  10. {
  11.     int lgn = int(log2(n)+0.01);
  12.     rev[0] = 0;
  13.     for (int i = 1; i < n; i++) rev[i] = (rev[i>>1]>>1)|((1<<(lgn-1))*(i&1));
  14.     for (int i = 0; i < n; i++) A[i] = a[rev[i]];
  15.     for (int k = 2; k <= n; k <<= 1) {
  16.         Complex dw = Complex(cos(2*PI/k), flag*sin(2*PI/k));
  17.         for (int i = 0; i < n; i += k) {
  18.             Complex w = Complex(1, 0), u, v;
  19.             for (int j = 0; j < (k>>1); j++) {
  20.                 u = A[i+j], v = w*A[i+j+(k>>1)];
  21.                 A[i+j] = u+v, A[i+j+(k>>1)] = u-v;
  22.                 w *= dw;
  23.             }
  24.         }
  25.     }
  26.     for (int i = 0; i < n; i++)
  27.         a[i] = A[i]/(flag==1?Complex(1,0):Complex(n,0));
  28. }
  30. long long k[MAXN];
  31. int dat[MAXN];
  33. Complex a[MAXN], b[MAXN], c[MAXN];
  35. int main()
  36. {
  37.     scanf("%d", &n);
  38.     int N = 1, mx = 0;
  39.     for (int i = 0; i < n; i++) {
  40.         int t; scanf("%d", &t); dat[i] = t;
  41.         mx = max(mx, t);
  42.         a[t] += Complex(1, 0);
  43.         b[2*t] += Complex(1, 0);
  44.         c[3*t] += Complex(1, 0);
  45.     }
  46.     while (N <= mx*3) N<<=1;
  47.     fft(a, N, 1), fft(b, N, 1), fft(c, N, 1);
  48.     for (int i = 0; i < N; i++)
  49.         a[i]=(a[i]*a[i]*a[i]-Complex(3, 0)*a[i]*b[i]+Complex(2, 0)*c[i])/Complex(6, 0)+(a[i]*a[i]-b[i])/Complex(2, 0)+a[i];
  50.     fft(a, N, -1);
  51.     for (int i = 0; i < N; i++) {
  52.         k[i] += (long long)(a[i].real()+0.1);
  53.     }
  54.     for (int i = 0; i < N; i++)
  55.         if (k[i])
  56.             printf("%d %lld\n", i, k[i]);
  57.     return 0;
  58. }

Tarjan

bzoj2140 稳定婚姻

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 10005, MAXM = 100005;
  5. struct node {
  6.     int to, next;
  7. } edge[MAXM];
  8. int head[MAXN], top = 0;
  9. void push(int i, int j)
  10. { edge[++top] = (node){j, head[i]}, head[i] = top; }
  12. int dfn[MAXN], low[MAXN], stk[MAXN], instk[MAXN], stop = 0, dfs_top = 0;
  13. int gp[MAXN], gp_top = 0;
  14. int n, m, strtop = 0;
  15. map<string, int> tab;
  16. string str[MAXN];
  17. string s1, s2;
  19. void tarjan(int nd)
  20. {
  21.     stk[++stop] = nd, instk[nd] = 1, dfn[nd] = low[nd] = ++dfs_top;
  22.     for (int i = head[nd]; i; i = edge[i].next) {
  23.         int to = edge[i].to;
  24.         if (!dfn[to]) tarjan(to), low[nd] = min(low[nd], low[to]);
  25.         else if (instk[to]) low[nd] = min(low[nd], dfn[to]);
  26.     }
  27.     if (dfn[nd] == low[nd]) {
  28.         int now = 0; gp_top++;
  29.         // printf(" -- Group %d --\n", gp_top);
  30.         do {
  31.             now = stk[stop--];
  32.             gp[now] = gp_top;
  33.             instk[now] = 0;
  34.             // cerr << str[now] << " ";
  35.         } while (now != nd);
  36.         // puts("");
  37.     }
  38. }
  41. int cpx[MAXN], cpy[MAXN];
  43. int main()
  44. {
  45.     scanf("%d", &n);
  46.     for (int i = 1; i <= n; i++) {
  47.         cin >> s1 >> s2;
  48.         if (!tab.count(s1)) tab[s1] = ++strtop, str[strtop] = s1;
  49.         if (!tab.count(s2)) tab[s2] = ++strtop, str[strtop] = s2;
  50.         push(tab[s2], tab[s1]);
  51.         cpx[i] = tab[s1], cpy[i] = tab[s2];
  52.     }
  53.     scanf("%d", &m);
  54.     for (int i = 1; i <= m; i++) {
  55.         cin >> s1 >> s2;
  56.         push(tab[s1], tab[s2]);
  57.     }
  58.     for (int i = 1; i <= strtop; i++)
  59.         if (!dfn[i])
  60.             tarjan(i);
  61.     for (int i = 1; i <= n; i++)
  62.         if (gp[cpx[i]] == gp[cpy[i]])
  63.             puts("Unsafe");
  64.         else
  65.             puts("Safe");
  66.     return 0;
  67. }

dinic

CQOI2015 网络吞吐量

spfa居然写跪了...没救了这

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 2005, MAXM = 200005;
  5. struct node {
  6.     int to, next;
  7.     long long flow;
  8.     int neg;
  9. } edge[MAXM];
  10. int head[MAXN], top = 0;
  11. void push(int i, int j, long long f)
  12. {
  13.     ++top, edge[top] = (node){j, head[i], f, top+1}, head[i] = top;
  14.     ++top, edge[top] = (node){i, head[j], 0, top-1}, head[j] = top;
  15. }
  17. const long long inf = 23333333333333ll;
  18. int S, T, n, m;
  20. int lev[MAXN], vis[MAXN], bfstime = 0;
  21. queue<int> que;
  23. bool bfs()
  24. {
  25.     que.push(S), lev[S] = 0, vis[S] = ++bfstime;
  26.     while (!que.empty()) {
  27.         int t = que.front(); que.pop();
  28.         for (int i = head[t]; i; i = edge[i].next) {
  29.             int to = edge[i].to;
  30.             long long d = edge[i].flow;
  31.             if (!d || vis[to] == bfstime) continue;
  32.             vis[to] = bfstime, que.push(to), lev[to] = lev[t]+1;
  33.         }
  34.     }
  35.     return vis[T] == bfstime;
  36. }
  38. long long dfs(int nd, long long flow = inf)
  39. {
  40.     if (!flow || nd == T) return flow;
  41.     long long t, ans = 0;
  42.     for (int i = head[nd]; i; i = edge[i].next) {
  43.         int to = edge[i].to;
  44.         long long d = edge[i].flow;
  45.         if (!d || lev[to] != lev[nd]+1) continue;
  46.         t = dfs(to, min(flow, d));
  47.         ans += t, flow -= t;
  48.         edge[i].flow -= t, edge[edge[i].neg].flow += t;
  49.     }
  50.     if (flow) lev[nd] = -1;
  51.     return ans;
  52. }
  54. long long dinic()
  55. {
  56.     long long ans = 0;
  57.     while (bfs()) ans += dfs(S);
  58.     return ans;
  59. }
  61. long long dis[MAXN];
  62. int inq[MAXN];
  63. long long rk[MAXN];
  65. node g2[MAXM];
  66. int h2[MAXN], tp = 0;
  67. void push2(int i, int j, long long k)
  68. { ++tp, g2[tp] = (node){j, h2[i], k, 0}, h2[i] = tp; }
  70. void spfa()
  71. {
  72.     memset(dis, 127/3, sizeof dis);
  73.     memset(inq, 0, sizeof inq);
  74.     dis[S] = 0, que.push(S), inq[S] = 1;
  75.     while (!que.empty()) {
  76.         int t = que.front(); que.pop(), inq[t] = 0;
  77.         for (int i = h2[t]; i; i = g2[i].next) {
  78.             int to = g2[i].to, d = g2[i].flow;
  79.             if (dis[to] > dis[t] + d) {
  80.                 dis[to] = dis[t] + d;
  81.                 if (!inq[to])
  82.                     inq[to] = 1, que.push(to);
  83.             }
  84.         }
  85.     }
  86. }
  88. int main()
  89. {
  90.     scanf("%d%d", &n, &m), S = 1, T = n+n;
  91.     for (int i = 1; i <= m; i++) {
  92.         int u, v;
  93.         long long d; scanf("%d%d%lld", &u, &v, &d);
  94.         push2(u, v, d), push2(v, u, d);
  95.     }
  96.     for (int i = 1; i <= n; i++) scanf("%lld", &rk[i]);
  97.     spfa();
  98.     for (int i = 1; i <= n; i++)
  99.         for (int j = h2[i]; j; j = g2[j].next) {
  100.             int to = g2[j].to;
  101.             long long d = g2[j].flow;
  102.             if (dis[to] == dis[i] + d) {
  103.                 push(i+n, to, inf);
  104.                 // cout << i << "--" << d << "->" << to << endl;
  105.             }
  106.         }
  107.     push(1, n+1, inf), push(n, n+n, inf);
  108.     for (int i = 2; i < n; i++) push(i, i+n, rk[i]);
  109.     cout << dinic() << endl;
  110.     return 0;
  111. }

spfa费用流

[Noi2008]志愿者招募

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 2005, MAXM = 100005;
  5. struct node {
  6.     int to, next;
  7.     long long flow, cost;
  8.     int neg;
  9. } edge[MAXM];
  10. int head[MAXN], top = 0, S = 2000, T = 2001;
  11. long long inf = 23333333333333ll;
  12. void push(int i, int j, long long f, long long c)
  13. {
  14.     ++top, edge[top] = (node){j, head[i], f, c, top+1}, head[i] = top;
  15.     ++top, edge[top] = (node){i, head[j], 0, -c, top-1}, head[j] = top;
  16. }
  17. void push_lim(int i, int j, long long mf)
  18. {
  19.     push(S, j, mf, 0), push(i, T, mf, 0);
  20.     push(i, j, inf, 0);
  21. }
  22. long long dis[MAXN];
  23. int vis[MAXN], pre[MAXN], pre_edge[MAXN], n, m;
  24. queue<int> que;
  25. bool spfa(long long &cost)
  26. {
  27.     memset(dis, 127/3, sizeof dis);
  28.     memset(vis, 0, sizeof vis);
  29.     memset(pre, 0, sizeof pre);
  30.     memset(pre_edge, 0, sizeof pre_edge);
  31.     vis[S] = 1, dis[S] = 0, que.push(S);
  32.     while (!que.empty()) {
  33.         int t = que.front(); que.pop(); vis[t] = 0;
  34.         for (int i = head[t]; i; i = edge[i].next) {
  35.             int to = edge[i].to, c = edge[i].cost;
  36.             if (!edge[i].flow) continue;
  37.             if (dis[to] > dis[t] + c) {
  38.                 dis[to] = dis[t] + c;
  39.                 pre[to] = t, pre_edge[to] = i;
  40.                 if (!vis[to])
  41.                     vis[to] = 1, que.push(to);
  42.             }
  43.         }
  44.     }
  45.     if (dis[T] >= inf) return 0;
  46.     long long mf = inf;
  47.     for (int i = T; i != S; i = pre[i]) mf = min(mf, edge[pre_edge[i]].flow);
  48.     for (int i = T; i != S; i = pre[i]) edge[pre_edge[i]].flow -= mf, edge[edge[pre_edge[i]].neg].flow += mf;
  49.     cost += dis[T]*mf;
  50.     return 1;
  51. }
  53. long long mcf()
  54. {
  55.     long long ans = 0;
  56.     while (spfa(ans));
  57.     return ans;
  58. }
  60. int main()
  61. {
  62.     scanf("%d%d", &n, &m);
  63.     for (int i = 1; i <= n; i++) {
  64.         long long u; scanf("%lld", &u);
  65.         push_lim(i, i+1, u);
  66.     }
  67.     for (int i = 1; i <= m; i++) {
  68.         int l, r; long long cost;
  69.         scanf("%d%d%lld", &l, &r, &cost);
  70.         push(r+1, l, inf, cost);
  71.     }
  72.     cout << mcf() << endl;
  73.     return 0;
  74. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注