盒子
盒子
文章目录
  1. 三分法
  2. 负环
  3. ST表
  4. manacher算法
  5. 线性基
  6. 双排列的最长公共子序列
  7. 最近公共祖先(LCA)
  8. 缩点
  9. 文艺平衡树
  10. 最小生成树
  11. 线性筛素数
  12. 线段树 1
  13. 二分图匹配
  14. 割点(割顶)
  15. 卢卡斯定理
  16. 高斯消元法
  17. 网络最大流
  18. 最小费用最大流
  19. floyd 最小环
  20. KMP字符串匹配
  21. AC自动机(简单版)

noip 模板复习计划

三分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 50;

int n;
ld l, r, a[N];

ld get(ld x) {
ld res = 0;
for(int i = n ; i >= 0 ; -- i) {
res = res * x + a[i];
}
return res;
}

int main() {
cin >> n >> l >> r;
for(int i = n ; i >= 0 ; -- i) cin >> a[i];
for(int i = 1 ; i <= 100 ; ++ i) {
ld len = (r - l) / 3;
ld ml = l + len, mr = l + len * 2;
if(get(ml) > get(mr)) {
r = mr;
} else {
l = ml;
}
}
cout << fixed << setprecision(5) << l << endl;
}

负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 2010, M = 6010, inf = 0x3f3f3f3f;
int n, m;
int head[N], rest[M], w[M], to[M], tot;
void add(int u, int v, int wi) {
to[++ tot] = v, w[tot] = wi, rest[tot] = head[u], head[u] = tot;
}
int dis[N], cnt[N], inq[N];

void sol() {
cin >> n >> m;
for(int i = 1 ; i <= n ; ++ i) {
inq[i] = 0;
head[i] = 0;
dis[i] = inf;
cnt[i] = 0;
}
tot = 0;
for(int i = 1, u, v, w ; i <= m ; ++ i) {
cin >> u >> v >> w;
if(w < 0) add(u, v, w);
else add(u, v, w), add(v, u, w);
}
queue<int> q;
q.push(1), dis[1] = 0, inq[1] = 1;
while(q.size()) {
int u = q.front(); q.pop();
inq[u] = 0;
if(++ cnt[u] > n) {
puts("YE5");
return ;
}
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i], w = :: w[i];
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if(!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
}
puts("N0");
}

int main() {
int T; cin >> T;
while(T --) sol();
}

ST表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], f[N][21];
int lg[N];

void init() {
lg[0] = -1;
for(int i = 1 ; i <= n ; ++ i) lg[i] = lg[i >> 1] + 1;
for(int i = 1 ; i <= n ; ++ i) f[i][0] = a[i];
for(int j = 1 ; j <= 20 ; ++ j)
for(int i = 1 ; i + (1 << j) - 1 <= n ; ++ i)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int sol(int l, int r) {
int k = lg[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
scanf("%d%d", &n, &m);
for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]);
init();
for(int i = 1, l, r ; i <= m ; ++ i) {
scanf("%d%d", &l, &r);
printf("%d\n", sol(l, r));
}
}

manacher算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 22000000 + 10;

int n, rig[N];
char str[N];

int main() {
scanf("%s", str + 1), n = strlen(str + 1);
for(int i = n ; i ; -- i) {
str[2 * i] = str[i];
}
for(int i = 1 ; i <= 2 * n + 1 ; i += 2) {
str[i] = '#';
}
n = 2 * n + 1;
for(int i = 1, pos = -1, mxr = -1 ; i <= n ; ++ i) {
rig[i] = i > mxr ? 1 : min(mxr - i, rig[2 * pos - i]);
while(i - rig[i] >= 1 && i + rig[i] <= n && str[i - rig[i]] == str[i + rig[i]]) ++ rig[i];
if(i + rig[i] - 1 > mxr) {
mxr = i + rig[i] - 1;
pos = i;
}
}
int ans = 0;
for(int i = 1 ; i <= n ; ++ i) {
ans = max(ans, rig[i] - 1);
}
printf("%d\n", ans);
}

线性基

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 60;
int n; ll a[N];

int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; ++ i) {
ll x; scanf("%lld", &x);
for(int j = 50 ; ~ j ; -- j) {
if((x >> j) & 1) {
if(!a[j]) {
a[j] = x;
break;
}
x ^= a[j];
}
}
}
ll ans = 0;
for(int i = 50 ; ~ i ; -- i)
if((ans ^ a[i]) > ans)
ans ^= a[i];
printf("%lld\n", ans);
}

双排列的最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;
int n, a[N], b[N], c[N], e[N], d[N], f[N], ans;
void add(int x, int y) {
for( ; x <= n ; x += x & -x)
d[x] = max(d[x], y);
}
int ask(int x) {
int r = 0;
for( ; x ; x -= x & -x)
r = max(r, d[x]);
return r;
}

int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]);
for(int i = 1 ; i <= n ; ++ i) scanf("%d", &b[i]), e[b[i]] = i;
for(int i = 1 ; i <= n ; ++ i) c[i] = e[a[i]];
for(int i = 1 ; i <= n ; ++ i) {
ans = max(ans, f[i] = ask(c[i]) + 1);
add(c[i], f[i]);
}
printf("%d\n", ans);
}

最近公共祖先(LCA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 10;
int n, m, root;
int head[N], rest[N * 2], to[N * 2], tot;
void add(int u, int v) {
to[++ tot] = v, rest[tot] = head[u], head[u] = tot;
}
int fa[N][21], dep[N];
void dfs(int u) {
dep[u] = dep[fa[u][0]] + 1;
for(int i = 1 ; i <= 20 ; ++ i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i];
if(v == fa[u][0]) continue;
fa[v][0] = u;
dfs(v);
}
}
int getlca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = 20 ; ~ i ; -- i)
if(dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if(u == v) return u;
for(int i = 20 ; ~ i ; -- i)
if(fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}

int main() {
scanf("%d%d%d", &n, &m, &root);
for(int i = 1, u, v ; i < n ; ++ i) {
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
dfs(root);
for(int i = 1, u, v ; i <= m ; ++ i) {
scanf("%d%d", &u, &v);
printf("%d\n", getlca(u, v));
}
}

缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
vector<int> G[N], g[N];
int n, m, a[N];

int dfn[N], low[N], clk, sta[N], top, ins[N], cnt, sum[N], bel[N];

void dfs(int u) {
sta[++ top] = u, ins[u] = 1;
dfn[u] = low[u] = ++ clk;
for(int i = 0 ; i < G[u].size() ; ++ i) {
int v = G[u][i];
if(!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if(ins[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]) {
int v; ++ cnt;
do {
v = sta[top --]; ins[v] = 0;
bel[v] = cnt;
sum[cnt] += a[v];
} while(v != u);
}
}

int f[N];

int go(int u) {
if(f[u] != -1) return f[u];
f[u] = 0;
for(int i = 0 ; i < g[u].size() ; ++ i) {
int v = g[u][i];
f[u] = max(f[u], go(v));
}
return f[u] += sum[u];
}

int main() {
memset(f, -1, sizeof f);
scanf("%d%d", &n, &m);
for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]);
for(int i = 1, u, v ; i <= m ; ++ i) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
}
for(int i = 1 ; i <= n ; ++ i)
if(!dfn[i])
dfs(i);
for(int u = 1 ; u <= n ; ++ u) {
for(int i = 0 ; i < G[u].size() ; ++ i) {
int v = G[u][i];
int x = bel[u], y = bel[v];
if(x != y) {
g[x].push_back(y);
}
}
}
int ans = 0;
for(int i = 1 ; i <= cnt ; ++ i)
ans = max(ans, go(i));
printf("%d\n", ans);
}

文艺平衡树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10;

typedef pair<int, int> pii;
int root, sz[N], ch[N][2], tot, val[N], fix[N], rev[N];

int nd(int x) {
return val[++ tot] = x, sz[tot] = 1, tot;
}

void push(int x) {
if(x && rev[x]) {
swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1, rev[ch[x][1]] ^= 1;
rev[x] = 0;
}
}

int up(int x) {
return sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1, x;
}

int merge(int x, int y) {
push(x), push(y);
if(!x || !y) return x | y;
if(fix[x] < fix[y]) {
ch[x][1] = merge(ch[x][1], y);
return up(x);
} else {
ch[y][0] = merge(x, ch[y][0]);
return up(y);
}
}

pii split(int x, int k) {
pii r;
if(x) {
push(x);
if(sz[ch[x][0]] >= k) {
r = split(ch[x][0], k);
ch[x][0] = r.second, r.second = x;
} else {
r = split(ch[x][1], k - sz[ch[x][0]] - 1);
ch[x][1] = r.first, r.first = x;
}
up(x);
}
return r;
}

void dfs(int u) {
if(!u) return ;
push(u);
dfs(ch[u][0]);
printf("%d ", val[u]);
dfs(ch[u][1]);
}

int main() {
srand((unsigned long long) new char);
int n, m; scanf("%d%d", &n, &m);
for(int i = 1 ; i <= n ; ++ i) fix[i] = i; random_shuffle(fix + 1, fix + 1 + n);
for(int i = 1 ; i <= n ; ++ i) {
root = merge(root, nd(i));
}
for(int i = 1, l, r ; i <= m ; ++ i) {
scanf("%d%d", &l, &r);
pii x = split(root, r);
pii y = split(x.first, l - 1);
rev[y.second] ^= 1;
root = merge(merge(y.first, y.second), x.second);
}
dfs(root);
}

最小生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
struct E {
int u, v, w;
} e[N];
bool operator < (E a, E b) {
return a.w < b.w;
}
long long ans;
int fa[N];
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }
int main() {
int n, m; scanf("%d%d", &n, &m);
for(int i = 1 ; i <= m ; ++ i)
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
sort(e + 1, e + 1 + m);
for(int i = 1 ; i <= n ; ++ i) fa[i] = i;
for(int i = 1 ; i <= m ; ++ i) {
int u = e[i].u, v = e[i].v, w = e[i].w;
if(get(u) != get(v)) {
fa[get(u)] = get(v);
ans += w;
}
}
for(int i = 1 ; i <= n ; ++ i)
if(get(i) != get(1))
return puts("orz"), 0;
printf("%lld\n", ans);
}

线性筛素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int N = 10000000 + 10;
int pri[N], tot; bool vis[N];

int main() {
int n, m; scanf("%d%d", &n, &m);
vis[1] = 1;
for(int i = 2 ; i <= n ; ++ i) {
if(!vis[i]) pri[++ tot] = i;
for(int j = 1 ; j <= tot && i * pri[j] <= n ; ++ j) {
vis[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
for(int i = 1, x ; i <= m ; ++ i) {
scanf("%d", &x);
puts(vis[x] ? "No" : "Yes");
}
}

线段树 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 100000 * 10 + 10;

ll tag[N], sum[N];
int n, m;


#define lc (id << 1)
#define rc (id << 1 | 1)
void build(int id, int l, int r) {
int mid = (l + r) >> 1;
if(l == r) {
scanf("%lld", &sum[id]);
} else {
build(lc, l, mid), build(rc, mid + 1, r);
sum[id] = sum[lc] + sum[rc];
}
}

void push(int id, int l, int r) {
if(tag[id]) {
sum[id] += tag[id] * (r - l + 1);
tag[lc] += tag[id], tag[rc] += tag[id];
tag[id] = 0;
}
}

void up(int id, int l, int r) {
int mid = (l + r) >> 1;
push(lc, l, mid), push(rc, mid + 1, r);
sum[id] = sum[lc] + sum[rc];
}

void modify(int id, int l, int r, int ql, int qr, ll x) {
int mid = (l + r) >> 1;
push(id, l, r);
if(ql <= l && r <= qr) {
tag[id] += x;
return ;
} else if(qr <= mid) {
modify(lc, l, mid, ql, qr, x);
} else if(ql >= mid + 1) {
modify(rc, mid + 1, r, ql, qr, x);
} else {
modify(lc, l, mid, ql, mid, x);
modify(rc, mid + 1, r, mid + 1, qr, x);
}
up(id, l, r);
}

ll ask(int id, int l, int r, int ql, int qr) {
int mid = (l + r) >> 1;
push(id, l, r);
if(ql <= l && r <= qr) {
return sum[id];
} else if(qr <= mid) {
return ask(lc, l, mid, ql, qr);
} else if(ql >= mid + 1) {
return ask(rc, mid + 1, r, ql, qr);
} else {
return ask(lc, l, mid, ql, mid) + ask(rc, mid + 1, r, mid + 1, qr);
}
}

int main() {
scanf("%d%d", &n, &m);
build(1, 1, n);
for(int i = 1, op, l, r ; i <= m ; ++ i) {
scanf("%d%d%d", &op, &l, &r);
if(op == 1) {
ll k; scanf("%lld", &k);
modify(1, 1, n, l, r, k);
} else {
printf("%lld\n", ask(1, 1, n, l, r));
}
}
}

二分图匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 10;
int mat[N], n, m, e;
int a[N][N], T, vis[N], ans;

int dfs(int u) {
for(int v = 1 ; v <= m ; ++ v) {
if(a[u][v] && vis[v] != T) {
vis[v] = T;
if(!mat[v] || dfs(mat[v])) {
mat[v] = u;
return 1;
}
}
}
return 0;
}

int main() {
scanf("%d%d%d", &n, &m, &e);
for(int i = 1, u, v ; i <= e ; ++ i) {
scanf("%d%d", &u, &v);
if(v > m) continue;
a[u][v] = 1;
}
for(int i = 1 ; i <= n ; ++ i) {
++ T;
if(dfs(i)) {
++ ans;
}
}
printf("%d\n", ans);
}

割点(割顶)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int N = 20000 + 10, M = 200000 + 10;
int n, m;
int head[N], rest[M], to[M], tot = 1, ans;
void add(int u, int v) {
to[++ tot] = v, rest[tot] = head[u], head[u] = tot;
}

int dfn[N], low[N], clk, cut[N], root;
void dfs(int u, int fr) {
dfn[u] = low[u] = ++ clk;
int tot = 0;
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i];
if(i == fr) continue;
if(!dfn[v]) {
dfs(v, i);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
++ tot;
if(tot > 1 || u != root) {
cut[u] = 1;
}
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
ans += cut[u];
}

int main() {
scanf("%d%d", &n, &m);
for(int i = 1, u, v ; i <= m ; ++ i) {
scanf("%d%d", &u, &v);
if(u == v) continue;
add(u, v), add(v, u);
}
for(int i = 1 ; i <= n ; ++ i)
if(!dfn[i])
dfs(root = i, 0);
printf("%d\n", ans);
for(int i = 1 ; i <= n ; ++ i)
if(cut[i])
printf("%d ", i);
}

卢卡斯定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 2e5 + 10;
ll n, m, p, fac[N], invfac[N];
ll pw(ll a, ll b) {
ll r = 1;
for( ; b ; b >>= 1, a = a * a % p)
if(b & 1)
r = r * a % p;
return r;
}

ll C(ll n, ll m) {
if(n < m) return 0;
if(n < p) return fac[n] * invfac[m] % p * invfac[n - m] % p;
return C(n / p, m / p) * C(n % p, m % p) % p;
}

void sol() {
cin >> n >> m >> p;
if(p == 1) {
cout << 0 << endl;
return ;
}
fac[0] = invfac[0] = 1;
for(int i = 1 ; i < p ; ++ i) fac[i] = fac[i - 1] * i % p;
invfac[p - 1] = pw(fac[p - 1], p - 2);
for(int i = p - 2 ; i >= 1 ; -- i) invfac[i] = invfac[i + 1] * (i + 1) % p;
cout << C(n + m, m) << endl;
}

int main() {
int T; cin >> T;
while(T --) sol();
}

高斯消元法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N = 110;
int n; ld a[N][N];

int main() {
ios :: sync_with_stdio(0);
cin >> n;
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= n + 1 ; ++ j)
cin >> a[i][j];
for(int i = 1 ; i <= n ; ++ i) {
int ch = i;
for(int j = i ; j <= n ; ++ j)
if(fabs(a[j][i]) > fabs(a[ch][i]))
ch = j;
if(fabs(a[ch][i]) < 1e-7) {
cout << "No Solution" << endl;
return 0;
}
for(int j = i ; j <= n + 1 ; ++ j)
swap(a[i][j], a[ch][j]);
for(int j = i + 1 ; j <= n ; ++ j) {
ld t = a[j][i] / a[i][i];
for(int k = i ; k <= n + 1 ; ++ k) {
a[j][k] -= a[i][k] * t;
}
}
}

for(int i = n ; i >= 1 ; -- i) {
a[i][n + 1] /= a[i][i];
for(int j = i - 1 ; j >= 1 ; -- j) {
a[j][n + 1] -= a[j][i] * a[i][n + 1];
}
}

for(int i = 1 ; i <= n ; ++ i) {
cout << fixed << setprecision(2) << a[i][n + 1] << endl;
}
}

网络最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;
int head[N], rest[M], to[M], w[M], tot = 1;

void add(int u, int v, int w) {
to[++ tot] = v, :: w[tot] = w, rest[tot] = head[u], head[u] = tot;
}

int n, m, s, t;

int dis[N];

bool bfs() {
for(int i = 1 ; i <= n ; ++ i) dis[i] = -1;
dis[s] = 1;
queue<int> q; q.push(s);
while(q.size()) {
int u = q.front(); q.pop();
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i];
if(w[i] && dis[v] == -1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t] != -1;
}

int cur[N];
int dfs(int u, int flow) {
int use = 0;
if(u == t || !flow) return flow;
for(int &i = cur[u] ; i ; i = rest[i]) {
int v = to[i];
if(dis[v] == dis[u] + 1) {
int a = dfs(v, min(flow - use, w[i]));
use += a;
w[i] -= a;
w[i ^ 1] += a;
if(use == flow) break;
}
}
if(!use) dis[u] = -1;
return use;
}

int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1, u, v, w ; i <= m ; ++ i) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, 0);
}
int ans = 0;
while(bfs()) {
for(int i = 1 ; i <= n ; ++ i) cur[i] = head[i];
ans += dfs(s, inf);
}
printf("%d\n", ans);
}

最小费用最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 1e5 + 10, inf = 0x3f3f3f3f;
int head[N], rest[M], from[M], to[M], w[M], co[M], tot = 1;
void add(int u, int v, int w, int co) {
from[++ tot] = u, to[tot] = v, :: w[tot] = w, :: co[tot] = co, rest[tot] = head[u], head[u] = tot;
}
int n, m, s, t;

int dis[N], inq[N], pre[N];
bool spfa() {
for(int i = 1 ; i <= n ; ++ i) dis[i] = inf, pre[i] = 0;
queue<int> q;
q.push(s), inq[s] = 1, dis[s] = 0;
while(q.size()) {
int u = q.front(); q.pop(); inq[u] = 0;
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i], co = :: co[i];
if(w[i] && dis[v] > dis[u] + co) {
dis[v] = dis[u] + co;
pre[v] = i;
if(!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
}
return dis[t] != inf;
}

int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1, u, v, w, co ; i <= m ; ++ i) {
scanf("%d%d%d%d", &u, &v, &w, &co);
add(u, v, w, co), add(v, u, 0, -co);
}
int mxf = 0, sum = 0;
while(spfa()) {
int mn = inf;
for(int i = pre[t] ; i ; i = pre[from[i]]) {
mn = min(mn, w[i]);
}
for(int i = pre[t] ; i ; i = pre[from[i]]) {
w[i] -= mn;
w[i ^ 1] += mn;
}
mxf += mn;
sum += mn * dis[t];
}
printf("%d %d\n", mxf, sum);
}

floyd 最小环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10, inf = 0x3f3f3f3f;
int n, m, a[N][N], b[N][N];

void sol() {
memset(a, 0x3f, sizeof a);
memset(b, 0x3f, sizeof b);
for(int i = 1, u, v, w ; i <= m ; ++ i) {
scanf("%d%d%d", &u, &v, &w);
a[v][u] = a[u][v] = min(a[u][v], w);
b[v][u] = b[u][v] = min(b[u][v], w);
}
int ans = inf;
for(int k = 1 ; k <= n ; ++ k) {
for(int i = 1 ; i <= k ; ++ i) {
for(int j = i + 1 ; j <= k ; ++ j) {
if(b[i][k] != inf && b[k][j] != inf && a[i][j] != inf) {
ans = min(ans, b[i][k] + b[k][j] + a[i][j]);
}
}
}
for(int i = 1 ; i <= n ; ++ i) {
for(int j = 1 ; j <= n ; ++ j) {
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}
}
}
if(ans == inf) puts("It's impossible.");
else printf("%d\n", ans);
}
int main() {
while(scanf("%d%d", &n, &m) == 2) sol();
}

KMP字符串匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 2000000 + 10;
char s[N], t[N]; int n;
int nxt[N];

int main() {
scanf("%s%s", s + 1, t + 1);
int lens = strlen(s + 1);
int lent = strlen(t + 1);
strcat(t + 1, ".");
strcat(t + 1, s + 1);
n = strlen(t + 1);
for(int i = 2, j = 0 ; i <= n ; ++ i) {
while(j && t[i] != t[j + 1]) j = nxt[j];
if(t[i] == t[j + 1]) ++ j;
nxt[i] = j;
if(nxt[i] == lent) {
printf("%d\n", i - lent - 1 - lent + 1);
}
}
for(int i = 1 ; i <= lent ; ++ i)
printf("%d ", nxt[i]);
}

AC自动机(简单版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n; char s[N];
int ch[N][26], tot, val[N], fail[N];

int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; ++ i) {
scanf("%s", s + 1);
int x = 0; for(int j = 1 ; s[j] ; ++ j) {
int c = s[j] - 'a';
if(!ch[x][c]) ch[x][c] = ++ tot;
x = ch[x][c];
}
val[x] ++;
}
queue<int> q;
for(int i = 0 ; i < 26 ; ++ i)
if(ch[0][i])
q.push(ch[0][i]), fail[ch[0][i]] = 0;
while(q.size()) {
int u = q.front(); q.pop();
for(int i = 0 ; i < 26 ; ++ i) {
if(ch[u][i]) {
fail[ch[u][i]] = ch[fail[u]][i];
q.push(ch[u][i]);
} else {
ch[u][i] = ch[fail[u]][i];
}
}
}
scanf("%s", s + 1);
int ans = 0;
for(int x = 0, i = 1 ; s[i] ; ++ i) {
int c = s[i] - 'a';
x = ch[x][c];
for(int j = x ; j && val[j] != -1 ; j = fail[j]) {
ans += val[j];
val[j] = -1;
}
}
printf("%d\n", ans);
}
支持一下
扫一扫,支持nekko
  • 微信扫一扫