Mengzelev's Blog

自己看得惯的板子整理

Word count: 3,064 / Reading time: 18 min
2019/04/19 Share

动态规划

状态压缩dp

dfs版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dfs(int i, int rnd, int status) {
int j;
if (status == two[num] - 1) return 0;
if (f[i][status] > 0) return f[i][status];
int q = 1e9;
for (j = num; j > 0; --j) {
int temp = 1 << (j - 1);
if (j != i && (!(status & temp))) {
if (q > dfs(j, rnd + 1, status | temp) + a[need[i]][need[j]]) {
q = dfs(j, rnd + 1, status | temp) + a[need[i]][need[j]];
c[i][status] = j;
}
}
}
f[i][status] = q;
return q;
}

bfs版

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
void bfs(int start) {
memset(s, 0, sizeof(s));
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(start);
vis[start] = true;
s[start] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = 1; i <= m; ++i) {
int v1 = u + ok[i];
int v2 = u - ok[i];
if (v1 <= n && !vis[v1]) {
Q.push(v1);
s[v1] = s[u] + 1;
vis[v1] = true;
}
if (v2 >= 0 && !vis[v2]) {
Q.push(v2);
s[v2] = s[u] + 1;
vis[v2] = true;
}
}
}
}


int dp() {
for(int i = 0; i < 20; ++i) e[i] = (1 << i);
int sn = 1 << cnt1; //状态数
for(int i = 1; i < sn; ++i) f[i] = INF;
f[0] = 0;
for(int i = 0; i < sn; ++i) {
int j = 0;
while(i & e[j]) ++j;
for(int p = j + 1; p < cnt1; ++p) {
if(!(i & e[p]) && dist[p+1][j+1]) {
f[i | e[j] | e[p]] = min(f[i | e[j] | e[p]], f[i] + dist[p+1][j+1]);
}
}
}
return f[sn-1];

}

并查集

普通并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//别忘了初始化f[i]=i
int find(int x){
int root = f[x];
while(root != f[root]) root = f[root];
int y = f[x];
while(f[x] != root){
f[x] = f[y];
y = f[y];
}
return f[x];
}

void unite(a, b){
int fa = find(a);
int fb = find(b);
if(fa != fb) f[fa] = fb;
}

带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int find(int x){
if(f[x] == x) return x;
int temp = f[x];
f[x] = find(temp);
rel[x] = (rel[x] + rel[temp]) % 3;
//rel[x]初始化为全0
return f[x];
}

void unite(int d, int x, int y){
int fx = find(x);
int fy = find(y);
if(fx != fy){
f[fy] = fx;
rel[fy] = (3 + d + rel[x] - rel[y]) % 3;
}
}

bool judge(int d, int x, int y){
if(d == 0) return (rel[x] == rel[y]);
if(d == 1) return ((3 - rel[x] + rel[y]) % 3 == d);
}

最小生成树

kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int kruskal() {
int ans = 0, cnt = 0;
for (int i = 1; i <= n; ++i) f[i] = i;
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; ++i) {
int fu = find(e[i].u);
int fv = find(e[i].v);
if (fu != fv) {
f[fv] = fu;
ans += e[i].weight;
cnt++;
if (cnt == n - 1) break;
}
}
return ans;
}

最短路

dijkstra

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
struct node{
int id; //序号,找边权用
int d;
bool operator < (const node &y) const {
return d < y.d;
}
}vertex[MAXN] = {};

double dijkstra(){
priority_queue <node> q;
vertex[0].d = 0;
q.push(vertex[0]);

while(!q.empty()){
node u = q.top();
q.pop();

for(int i = 0; i < son[u.id].size(); ++i){
int vid = son[u.id][i];
double weight = w[u.id][i];
if(vertex[vid].d < u.d) continue;
if(vertex[vid].d > u.d + weight){
vertex[vid].d = u.d + weight;
q.push(vertex[vid]);
}
}
}
}

floyd

1
2
3
4
5
6
7
8
void floyd(){
for(int k = 0; k < n; ++k)
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j){
if(map[i][j] > map[i][k] + map[k][j])
map[i][j] = map[i][k] + map[k][j];
}
}

各种tarjan

有向图强连通分量数

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
//dfn[u] u的时间戳
//low[u] u或u的子树能够追溯到的最早栈中节点
void tarjan(int u){
dfn[u] = low[u] = ++cnt;
vis[u] = true;
stack1[++index] = u;
for(int i = 0; i < son[u].size(); ++i){
int v = son[u][i];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]); //u-v is a back edge
}

if(low[u] == dfn[u]){
scnum ++; //强连通分量数
do{
belong[stack1[index]] = scnum;
num[scnum] ++;
vis[stack1[index]] = false;
index --;
}while(u != stack1[index + 1]);
}
return;
}

// for(int i = 1; i <= n; ++i){
// if(!dfn[i]) {
// cnt = 1;
// tarjan(i);
// }
// }

无向图割点与割边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void tarjan(int u, int pre){
int child = 0;
dfs_clock ++;
dfn[u] = low[u] = dfs_clock;
for(int i = 0; i < son[u].size(); ++i){
int v = son[u][i];
if(!dfn[v]){
tarjan(v,u);
child ++;
low[u] = min(low[u], low[v]);
if((u == 1 && child > 1) || (u != 1 && dfn[u] <= low[v])) {
cut.push_back(u); //割点判定
//iscut[u] = true;
}
if(low[v] > dfn[u])
bridge.push_back({min(u,v), max(u,v)}); //割边判定
}
else if(dfn[v] < dfn[u] && v != pre)
low[u] = min(low[u], dfn[v]);
}
return;
}
//tarjan(1,-1);

无向图双连通分量

点(边)双连通分量:若一个无向图中的去掉任意一个节点(一条边)都不会改变此图的连通性,即不存在割点(桥),则称作点(边)双连通图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void tarjan(int u, int pre){
dfs_clock ++;
dfn[u] = low[u] = dfs_clock;
for(int i = 0; i < son[u].size(); ++i){
int v = son[u][i];
if(!dfn[v]){
tarjan(v,u);
low[u] = min(low[u], low[v]);
}
else if(dfn[v] < dfn[u] && v != pre) low[u] = min(low[u], dfn[v]);
}
return;
}
//统计无向图的边双连通分量,在一个双连通分量中当且仅当low[u] == low[v]

欧拉图

有向图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool directed_euler(){
int moreout = 0;
int morein = 0;
for(int i = 'a'; i <= 'z'; ++i){
if(ver[i].indeg > ver[i].outdeg) {
if(ver[i].indeg == ver[i].outdeg + 1) morein ++;
else return false;
}
else if(ver[i].deg < ver[i].outdeg) {
if(ver[i].outdeg == ver[i].indeg + 1) moreout++;
else return false;
}
}
//printf("morein = %d, moreout = %d", morein, moreout);
if(morein <= 1 && moreout <= 1) return true;
else return false;
}
//判断连通有向图是否含欧拉迹
//至多一顶点出度=入度+1
//至多一顶点入度=出度+1
//其余顶点:入度=出度

无向图

1
2
3
4
5
6
7
bool undirected_euler(){
int odd = 0;
for(int i = 'a'; i <= 'z'; ++i)
if(ver[i].deg % 2 == 1) odd++;
if(odd == 0 || odd == 2) return true;
else return false;
};

哈密尔顿回路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void hamilton(){
path.push_back(1);
for(int i = 2; i <= n; ++i){
bool flag = false;
for(int j = 0; j < path.size() - 1; ++j){
if(map[path[j]][i] && map[i][path[j + 1]]){
path.insert(path.begin() + j + 1, i);
flag = true;
break;
}
}
if(flag) continue;
if(map[path.back()][i]) path.push_back(i);
else path.insert(path.begin(), i);
}
}

完美匹配

匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool find(int x){
for(int i = 1; i <= m; ++i){
if(map[x][i] && !vis[i]) {
vis[i] = true;
if(match[i] == 0 || find(match[i])){
match[i] = x;
return true;
}
}
}
return false;
}

for(int i = 1; i <= n; ++i) {
memset(vis, 0 , sizeof(vis));
if(find(i)) ans ++;
}

KM:最小权匹配

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
bool find(int i) {
S[i] = true;
for (int j = 1; j <= num; ++j) {
if (!T[j] && ls[i] + lt[j] == map[i][j]) {
T[j] = true;
if (!match[j] || find(match[j])) {
match[j] = i;
return true;
}
}
}
return false;
}

void relax() {
int relax_val = 1e9;
for(int i = 1; i <= min(n,m); ++i)
if(S[i]) {
for(int j = 1; j <= num; ++j)
if(!T[j] && ls[i] + lt[j] > map[i][j]) relax_val = min(relax_val, ls[i] + lt[j] - map[i][j]);
}
assert(relax_val > 0);

for (int i = 1; i <= num; ++i) {
if (S[i]) ls[i] -= relax_val;
if (T[i]) lt[i] += relax_val;
}
}

int KM() {
memset(match, 0, sizeof(match));
for (int i = 1; i <= min(m,n); ++i) {
ls[i] = 0;
for (int j = 1; j <= num; ++j) ls[i] = max(map[i][j], ls[i]);
}
for(int i = 1; i <= num; ++i) lt[i] = 0;

for (int i = 1; i <= min(n,m); ++i) {
while (1) {
memset(S, 0, sizeof(S));
memset(T, 0, sizeof(T));
if (find(i)) break;
else relax();
}
}
}

网络流

Dinic+当前弧优化

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
bool bfs() {
memset(depth, 0 , sizeof(depth));
queue <int> q;
q.push(s);
depth[s] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = 0; i < son[u].size(); ++i) {
int v = son[u][i];
if(map[u][v] > 0 && !depth[v]) {
depth[v] = depth[u] + 1;
q.push(v);
}
}
}
if(depth[t] == 0) return false;
else return true;
}

int dfs(int u, int dist) {
/*
* 寻找当前增广路径上的最小容量
*/
if(u == t) return dist;
for(int &i = cur[u]; i < son[u].size(); ++i) {
int v = son[u][i];
if(depth[v] == depth[u] + 1 && map[u][v] > 0) {
int minc = dfs(v, min(dist, map[u][v]));
if(minc > 0) {
map[u][v] -= minc;
map[v][u] += minc;
return minc;
}
}
}
return 0;
}

void dinic() {
while(bfs()) {
memset(cur, 0 , sizeof(cur));
while(int minc = dfs(s, INF)) {
ans += minc;
//printf("minc=%d\n",minc);
}
}
}

矩阵

高斯消元

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
void swap2row(int x, int y) {
for(int i = 1; i <= n + 1; ++i) swap(a[x][i], a[y][i]);
//printf("**swap row %d with row %d**\n",x,y);
}

void pivot_one(int x, int y) {
double temp = a[x][y];
if(temp == 1) return;
for(int i = y; i <= n + 1; ++i) a[x][i] /= temp;
//printf("**pivot one at row %d**\n", x);
}

void mul_and_add(int src, int dst, double cof) {
for(int i = 1; i <= n + 1; ++i) {
a[dst][i] -= a[src][i] * cof;
}
//printf("**mul row %d with %lf add to row %d**\n", src, cof, dst);
}

void print_matrix() {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) printf("%lf ", a[i][j]);
printf("| %lf\n", a[i][n + 1]);
}
printf("------------------------\n");
}

bool iszero(int row) {
for(int i = 1; i <= n + 1; ++i)
if(a[row][i] != 0) return false;
return true;
}

void Guass() {
int row = 1, col = 1;
bool ok = false;
while(row <= n && col <= n) {
//printf("Now row=%d, col=%d\n",row, col);
if(a[row][col] == 0.0) {
ok = false;
for(int i = row + 1; i <= n; ++i)
if(a[i][col] != 0) {
swap2row(row, i);
ok = true;
break;
}
if(ok == false) {col++; continue;}
//else print_matrix();
}
pivot_one(row,col);
if(col == n && row == n && a[row][col] == 1) return;
//print_matrix();
for(int i = 1; i <= n; ++i)
if(i != row && a[i][col] != 0) {
assert(a[row][col] != 0);
double cof = a[i][col] / a[row][col];
if(cof != 0) mul_and_add(row, i, cof);
assert(a[i][col] == 0);
}
//print_matrix();
row ++; col ++;
}
}

线性规划 – simplex单纯形算法

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
int sgn(double x) {
if (x < -EPS) return -1;
return x > EPS ? 1 : 0;
}

void pivot(int r, int c) {
swap(id[n + r], id[c]);
double x = -a[r][c];
a[r][c] = -1;
for (int i = 0; i <= n; ++i) a[r][i] /= x;
for (int i = 0; i <= m; ++i) {
if (sgn(a[i][c]) && i != r) {
x = a[i][c];
a[i][c] = 0;
for (int j = 0; j <= n; ++j) a[i][j] += x * a[r][j];
}
}
}

int simplex() {
/* important: revert symbols of conditions */
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
a[i][j] *= -1;
}
}
for (int i = 1; i <= n; ++i) id[i] = i;
/* initial-simplex */
while (true) {
int x = 0, y = 0;
for (int i = 1; i <= m; ++i) {
if (sgn(a[i][0]) < 0) { x = i; break; }
}
if (!x) break;
for (int i = 1; i <= n; ++i) {
if (sgn(a[x][i]) > 0) { y = i; break; }
}
if (!y) return -1; // infeasible
pivot(x, y);
}
/* solve-simplex */
while (true) {
int x = 0, y = 0;
for (int i = 1; i <= n; ++i) {
if (sgn(a[0][i]) > 0) {
x = i;
break;
}
}
// printf("choose x%d, cof=%d\n", x, a[0][x]);
if (!x) break; // finished
double w = 0, t = 0; //t是最苛刻的非基本变量能取到的最大值
bool f = true;
for (int i = 1; i <= m; ++i) {
if (sgn(a[i][x]) < 0) {
t = ((double)-a[i][0]) / ((double)a[i][x]);
// if(x==3) printf("t: -%d / %d = %.lf\n", a[i][0], a[i][x], t);
if (f || t < w) {
w = t, y = i, f = false;
}
}
}
if (!y) {
return 1;
} // unbounded
pivot(y, x);
}
for (int i = 1; i <= n; ++i) v[i] = 0;
for (int i = n + 1; i <= n + m; ++i) v[id[i]] = a[i - n][0];
return 0;
}

字符串匹配

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void build_kmp() {
int j = -1;
kmp[0] = -1;
for(int i = 1; i < len2; ++i) {
while(j >= 0 && s2[i] != s2[j + 1]) j = kmp[j];
if(s2[j + 1] == s2[i]) j ++;
kmp[i] = j;
}
}

void do_kmp() {
int j = -1;
for(int i = 0; i < len1; ++i) {
while(j >= 0 && s1[i] != s2[j + 1]) j = kmp[j];
if(s1[i] == s2[j + 1]) ++j;
if(j == len2 - 1) {
printf("%d\n", i - len2 + 2);
j = kmp[j];
ok = true;
}
}
}

字典树

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
struct Trie{
/*字典树*/
int tot, root;
int nxt[MAXN][26] = {};

Trie() {
tot = 1;
root = newNode();
}

int newNode() {
memset(nxt[tot], 0 ,sizeof(nxt[tot]));
return tot++;
}

void append(string s) {
int cur = root;
for(int i = 0; i < s.size(); ++i) {
int id = s[i] - 'a';
if(nxt[cur][id] == 0) nxt[cur][id] = newNode();
cur = nxt[cur][id];
}
}

void print() {
for(int i = 1; i < tot; ++i){
for(int j = 0 ; j < 26; ++j) {
if(nxt[i][j] != 0)
printf("S.nxt[%d][%c]=%d\n",i, j+'a', nxt[i][j]);
}
}
}

}S;

快速幂

1
2
3
4
5
6
7
8
9
10
11
ll qpow(ll a, ll n, ll mod) {
/*快速幂*/
ll ans = 1;
a %= mod;
while(n > 0) {
if(n & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
CATALOG
  1. 1. 动态规划
    1. 1.1. 状态压缩dp
      1. 1.1.1. dfs版
      2. 1.1.2. bfs版
  2. 2. 并查集
    1. 2.1. 普通并查集
    2. 2.2. 带权并查集
  3. 3. 最小生成树
    1. 3.1. kruskal
  4. 4. 最短路
    1. 4.1. dijkstra
    2. 4.2. floyd
  5. 5. 各种tarjan
    1. 5.1. 有向图强连通分量数
    2. 5.2. 无向图割点与割边
    3. 5.3. 无向图双连通分量
  6. 6. 欧拉图
    1. 6.1. 有向图
    2. 6.2. 无向图
    3. 6.3. 哈密尔顿回路
  7. 7. 完美匹配
    1. 7.1. 匈牙利算法
    2. 7.2. KM:最小权匹配
  8. 8. 网络流
    1. 8.1. Dinic+当前弧优化
  9. 9. 矩阵
    1. 9.1. 高斯消元
    2. 9.2. 线性规划 – simplex单纯形算法
  10. 10. 字符串匹配
    1. 10.1. KMP
    2. 10.2. 字典树
  11. 11. 快速幂