ACM C++ Code

个人码风规定

警告⚠

不用奇怪的define！ 少用神秘的位运算！ 拒绝各种邪教码风！

基础模板

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
#define INF 0x7fffffff
#define MAXN 200010
typedef long long LL;
using namespace std;

int main()
{
	
    return 0;
}

常用变量名

我大小写敏感（

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
T // 样例数
a b c // 单变量
x y z // for循环索引
i j k // 比较少用到
u v w // 节点和权重
n m // 节点个数/数组大小一类
l r // 左右边界
s // 字符串
q // 队列
st // 栈
ch // 字符
s[MAXN] // 数组
vis[MAXN] // 图论 是否到达过
e[MAXN] // 图论 边
t[MAXN] // 树（偶尔用）
d[MAXN] // 距离，或表示权重
dp[MAXN] // 动态规划
vector <int> g[MAXN] // 图论（邻接表）

tf // bool判断
ans // 答案
inp // 纯输入用
cnt // 计数
dis // 距离
tmp // 临时存储
MOD // 取模大数
maxn minn // 最大最小值

struct node{} // 节点

缩进/空格/函数名

所有函数/if/for等语句大括号换行 如果只有单语句可以省略大括号并接在后面
能加空格尽量加，除非忍不住
驼峰命名法 尽量不用下划线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int isNumber(int a) // 驼峰命名法
{ // 大括号换行
    for(int x = 1; x <= n; x++) // 空格党
    {
        if(a == 114514)
        {
            cout << "AAAAAAAAAAAAAH" << endl;
            return 1919810;
        }
        else a += b; // 省略大括号
    }

    for(int x = 1; x <= m; x++)
        if(a >= INF) cout << "N/A" << endl;
    // 有时候会这样写两层省略大括号
}

*关于索引：其实我一般数组、图论都是从1到n，但是有时候会出现字符串等特殊情况就用0到n-1

常用模板

主要还是曾经写的洛谷blog的模板，具体模板详解还得去看原文

慢慢搬运重制吧，还要验证正确性

基础算法

快读/快写

实际几乎没用过，打比赛基本不卡常，大数据IO用scanf/printf够了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int read()
{
    int a = 0, f = 1; char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){a = a * 10 + ch - 48;ch = getchar();}
    return a * f;
}

void write(int a)
{
	if(a < 0) {putchar('-'); a = -a;}
	if(a > 9) {write(a/10); putchar(a % 10 + '0');}
	else putchar(a + '0');
	return; 
}

二分答案

最基础最重要的算法之一
实际使用主要需要设计二分条件，即half函数

这里给一个例子：
在一个排好序的数组s里面寻找整数a的位置，时间复杂度$O(log(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int s[MAXN];

bool halfCheck(int mid, int a)
{
    return s[mid] >= a;
}

int binarySearch(int l, int r, int a)
{
    int re;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(halfCheck(mid, a))
        {
            r = mid - 1;
            re = mid;
        }
        else l = mid + 1;
    }
    return re;
}

快速排序

不会真的有人不用STL的sort，还自己写快排吧（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int s[MAXN];

void fastSort(int l, int r)
{
	if(l >= r) return;
	int i = l, j = r;
	while(i < j)
	{
		while(s[j] >= s[l] && i < j) j--;
		while(s[i] <= s[l] && i < j) i++;
		swap(s[i], s[j]);
	}
	swap(s[l], s[i]);
	fastSort(l, i - 1);
	fastSort(i + 1, r);
}

数学

快速幂

可以在$O(\log n)$的时间复杂度里求出$a^n\ \text{mod}\ m$

1
2
3
4
5
6
7
8
9
10
LL fastPow(LL a, LL n, LL m) // 一般要开long long
{
	LL ans = 1;
	while(n)
	{
		if(n & 1) ans *= a, ans %= m;
		a *= a, a %= m, n >>= 1;
	}
	return ans % m;
}

GCD 欧几里得算法

求a和b的最大公约数

1
2
3
4
5
int gcd(int a, int b)
{
	if(!b) return a;
	else return gcd(b, a % b);
}

EXGCD 扩展欧几里得算法

在求得a、b的最大公约数的同时，能找到整数x、y，满足贝祖等式
$$ax + by = \gcd(a, b)$$

1
2
3
4
5
void exgcd(int a, int b, int &x, int &y)
{
	if(!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

逆元

用$O(n)$的时间求1到n对模m的逆元
$$ax \equiv 1 \pmod{m}$$

1
2
3
4
int n, m, inv[MAXN];

inv[1] = 1;
for(int x = 2; x <= n; x++) inv[x] = (inv[m % x] * (m-m/x)) % m;

中国剩余定理

用于解以下一元线性同余方程组
$$
\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\ \ \ \vdots \\
x \equiv a_n \pmod{m_n}
\end{cases}
$$
注意配合前面的exgcd使用
考虑到实际情况一般答案会很大，建议开long long

1
2
3
4
5
6
7
8
9
10
11
12
int CRT(int n, int *a, int *m)
{
    int N = 1, ans = 0;
    for(int x = 1; x <= n; x++) N *= a[x];
    for(int x = 1; x <= n; x++)
    {
        int b = N / a[x], ny, tmp;
        exgcd(b, a[x], ny, tmp);
        ans = (ans + b * (ny < 0 ? ny + a[x] : ny) * m[x]) % N;
    }
    return ans;
}

图论

我是邻接表享受者😎
没有特殊说明默认全都是邻接表建图

最短路

SPFA

有向/无向图单源最短路，能求出st到任意一个点的最短路（无负环），时间复杂度最坏$O(nm)$，但实际上会比较快

如果有负环需要加一个cnt数组用于记录入队次数，SPFA里面里判断负环的方法是：记录每个节点入队的次数，如果某个点入队次数超过 n（点数），说明存在负环。

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
struct node
{
    int v, dis;
};

vector <node> g[MAXN];

int n, m, d[MAXN]; // 需要初始化d[i] = INF
bool vis[MAXN];

void SPFA(int st)
{
    queue <int> q;
    d[st] = 0;
    vis[st] = true;
    q.push(st);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = false;
        for(int x = 0; x < g[u].size(); x++)
        {
            int v = g[u][x].v, dis = g[u][x].dis;
            if(d[v] > d[u] + dis)
            {
                d[v] = d[u] + dis;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

Floyd

有向/无向图多源最短路，时间复杂度$O(n^3)$，代码思路简单所以复杂度也比较高，可以判负环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n, m;
int d[MAXN][MAXN];
bool findN;

void Floyd()
{
	findN = false;
	for(int z = 1; z <= n; z++)
		for(int x = 1; x <= n; x++)
			for(int y = 1; y <= n; y++)
				if(d[x][z] < INF && d[z][y] < INF)
					d[x][y] = min(d[x][y], d[x][z] + d[z][y]);
	for(int x = 1; x <= n; x++)
		if(d[x][x] < 0) findN = true; // 找到负环
}

然后main函数里要这样子初始化以及读边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    cin >> n >> m;
	for(int x = 0; x < n; x++)
		for(int y = 0; y < n; y++)
			d[x][y] = (x == y ? 0 : INF);
	
	for(int x = 1; x <= m; x++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		d[u][v] = min(d[u][v], w);
	}
}

最小生成树

Kruskal

给定一个无向图，求出最小生成树，模板这里是返回了最小生成树的边权之和，然后把相应的边存起来

时间复杂度$O(m \log m)$

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 edge
{
	int u, v, w;
} g[MAXN];

int n, m;
int fa[MAXN];
vector <edge> MST;

bool cmp(edge x, edge y)
{
	return x.w < y.w;
}

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int Kruskal()
{
	for(int x = 1; x <= n; x++) fa[x] = x;
	int ans = 0;
	sort(g+1, g+m+1, cmp);
	for(int x = 1; x <= m; x++)
	{
		int u = find(g[x].u), v = find(g[x].v);
		if(u == v) continue;
		fa[v] = u;
		ans += g[x].w;
		MST.push_back(g[x]);
	}
	return ans;
}

Tarjan

割点

无向图中用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
int n, m, cnt;
vector <int> g[MAXN];
int dfn[MAXN], low[MAXN];
bool isCut[MAXN];

void Tarjan(int u, int parent)
{
	low[u] = dfn[u] = ++cnt;
	int child = 0;
	for(int x = 0; x < g[u].size(); x++)
	{
		int v = g[u][x];
		if(!dfn[v])
		{
			Tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(parent != -1 && low[v] >= dfn[u]) isCut[u] = true;
			child++;
		}
		else if(v != parent) low[u] = min(low[u], dfn[v]);
	}
	if(parent == -1 && child >= 2) isCut[u] = true;
}

vector <int> getCutPoint()
{
	for(int x = 1; x <= n; x++) // 注意下标
		if(!dfn[x]) Tarjan(x, -1);
	vector <int> ans;
	for(int x = 1; x <= n; x++)
		if(isCut[x]) ans.push_back(x);
	return ans;
}

桥

无向图中用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
34
35
36
37
38
39
40
struct edge
{
	int u, v;
};

int n, m, cnt;
vector <int> g[MAXN];
int dfn[MAXN], low[MAXN];
vector <edge> ans;

void Tarjan(int u, int parent)
{
	low[u] = dfn[u] = ++cnt;
	for(int x = 0; x < g[u].size(); x++)
	{
		int v = g[u][x];
		if(v == parent) continue;
		if(!dfn[v])
		{
			Tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > dfn[u]) ans.push_back((edge){min(u,v), max(u,v)});
		}
		else low[u] = min(low[u], dfn[v]);
	}
}

bool cmp(edge x, edge y)
{
	if(x.u == y.u) return x.v < y.v;
	return x.u < y.u;
}

vector <edge> getBridge()
{
	for(int x = 1; x <= n; x++) // 注意下标
		if(!dfn[x]) Tarjan(x, -1);
	sort(ans.begin(), ans.end(), cmp);
	return ans;
}

强连通分量

有向图中用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
34
35
36
37
38
39
40
41
42
43
44
45
int n, m, cnt, colcnt;
vector <int> g[MAXN];
int dfn[MAXN], low[MAXN], color[MAXN];
bool vis[MAXN];
stack <int> st;

void Tarjan(int u)
{
	dfn[u] = low[u] = ++cnt;
	st.push(u);
	vis[u] = true;
	for(int x = 0; x < g[u].size(); x++)
	{
		int v = g[u][x];
		if(!dfn[v])
		{
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(vis[v]) low[u] = min(low[u], dfn[v]); // 找到环了
	}
	if(dfn[u] == low[u])
	{
		colcnt++;
		int v;
		do
		{
			v = st.top(); st.pop();
			vis[v] = false;
			color[v] = colcnt; // 染色
		} while(v != u);
	}
}

vector <int> ng[MAXN];

void newGraph() // 用颜色建新图
{
	for(int x = 0; x < n; x++)
		for(int y = 0; y < g[x].size(); y++)
		{
			int v = g[x][y];
			if(color[x] != color[v]) ng[color[x]].push_back(color[v]);
		}
}

拓扑排序

有向无环图中（DAG, Directed Acyclic Graph）的每一条有向边（u->v），在排序中顶点u必须在顶点v的前面

Kahn算法

基于入度的高效算法，还能检测不合法的环，时间复杂度$O(n+m)$

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
int n, m;
vector <int> g[MAXN];
int ind[MAXN];

vector <int> topoSort()
{
	vector <int> ans;
	queue <int> q;
	for(int x = 1; x <= n; x++) // 注意下标
		for(int y = 0; y < g[x].size(); y++) ind[g[x][y]]++; // 计算入度
	for(int x = 1; x <= n; x++)
		if(ind[x] == 0) q.push(x); // 将入度为0的点丢进序列
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		ans.push_back(u);
		for(int x = 0; x < g[u].size(); x++)
		{
			int v = g[u][x];
			ind[v]--;
			if(ind[v] == 0) q.push(v);
		}
	}
	if(ans.size() != n) cout << "FIND CIRCLE!" << endl; // 找到环，不合法
	return ans;
}

树

树的直径

跑两遍dfs找最远的两个点的距离，就是树的直径，时间复杂度$O(n)$

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
struct node
{
	int v, w;	
};

int n, m;
vector <node> g[MAXN];
bool vis[MAXN];
int maxDist, farNode;

void findFar(int u, int dist)
{
	vis[u] = true;
	if(dist > maxDist)
	{
		maxDist = dist;
		farNode = u;
	}
	for(int x = 0; x < g[u].size(); x++)
	{
		int v = g[u][x].v, w = g[u][x].w;
		if(!vis[v]) findFar(v, dist + w);
	}
}

int treeDiameter()
{
	memset(vis, 0, sizeof(vis));
	maxDist = 0;
	findFar(1, 0);

	memset(vis, 0, sizeof(vis));
	maxDist = 0;
	findFar(farNode, 0);

	return maxDist;
}

树的高度

换根DP，时间复杂度$O(n)$能求分别以1-n所有节点为根的树的高度

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
struct node
struct node
{
	int v, w;	
};

int n, m;
vector <node> g[MAXN];
int dp[MAXN], ht[MAXN];

void treeDepth(int u, int parent)
{
	dp[u] = 0;
	for(int x = 0; x < g[u].size(); x++)
	{
		int v = g[u][x].v, w = g[u][x].w;
		if(v == parent) continue;
		treeDepth(v, u);
		dp[u] = max(dp[u], dp[v] + w);
	}
}

void changeRoot(int u, int parent, int up)
{
	vector <int> pre, suf;
	for(int x = 0; x < g[u].size(); x++)
	{
		int v = g[u][x].v, w = g[u][x].w;
		if(v == parent) pre.push_back(up);
		else pre.push_back(dp[v] + w);
	}
	suf = pre;
	for(int x = 1; x < g[u].size(); x++) pre[x] = max(pre[x], pre[x-1]);
	for(int x = g[u].size() - 2; x >= 0; x--) suf[x] = max(suf[x], suf[x+1]);
	ht[u] = max(dp[u], up);
	for(int x = 0; x < g[u].size(); x++)
	{
		int v = g[u][x].v, w = g[u][x].w;
		if(v == parent) continue;
		int left = (x == 0 ? -INF : pre[x-1]);
		int right = (x == g[u].size()-1 ? -INF : suf[x+1]);
		int newUp = max(up, max(left, right)) + w;
		changeRoot(v, u, newUp);
	}
}

vector <int> treeHeight()
{
	treeDepth(0, -1);
	changeRoot(0, -1, 0);
	vector <int> re;
	for(int x = 0; x < n; x++) re.push_back(ht[x]);
	return re;
}

LCA

倍增求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
int n, m;
vector <int> g[MAXN];
int lg[MAXN], dep[MAXN], fa[MAXN][32];

void dfs(int u, int f)
{
	fa[u][0] = f;
	dep[u] = dep[f] + 1;
	for(int x = 1; x < 20; x++)
	{
		if (fa[u][x - 1] == 0) break;
		fa[u][x] = fa[fa[u][x - 1]][x - 1];
	}
	for(int x = 0; x < g[u].size(); x++)
		if(g[u][x] != f) dfs(g[u][x], u);
}

void initLCA(int root)
{
	lg[0] = -1;
	for(int x = 1; x <= n; x++) lg[x] = lg[x >> 1] + 1;
	dfs(root, 0);
}

int getLCA(int a, int b)
{
	if(dep[a] < dep[b]) swap(a, b);
	for (int i = 19; i >= 0; i--)
		if (dep[a] - (1 << i) >= dep[b]) a = fa[a][i];
	if(a == b) return a;
	for(int x = lg[dep[a]]; x >= 0; x--)
		if(fa[a][x] != fa[b][x]) a = fa[a][x], b = fa[b][x];
	return fa[a][0];
}

网络流

邻接表享受者😎

Dinic

时间复杂度$O(n^2m)$

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
struct node
{
	int v, rev, cap;
};

int n, m;
vector <node> g[MAXN];
int level[MAXN], iter[MAXN];

void addEdge(int u, int v, int cap)
{
	g[u].push_back((node){v, (int)g[v].size(), cap});
	g[v].push_back((node){u, (int)g[u].size()-1, 0}); // 反向边
}

void buildLevel(int st)
{
	for(int x = 0; x < n; x++) level[x] = -1;
	queue <int> q;
	level[st] = 0;
	q.push(st);
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int x = 0; x < g[u].size(); x++)
		{
			int v = g[u][x].v, cap = g[u][x].cap;
			if(cap > 0 && level[v] < 0)
			{
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
}

int DinicDFS(int u, int ed, int upToFlow)
{
	if(u == ed) return upToFlow;
	for(int x = iter[u]; x < g[u].size(); x++)
	{
		int v = g[u][x].v, rev = g[u][x].rev, cap = g[u][x].cap;
		if(cap > 0 && level[u] < level[v])
		{
			int d = DinicDFS(v, ed, min(upToFlow, cap));
			if(d > 0)
			{
				g[u][x].cap -= d;
				g[v][rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int Dinic(int st, int ed)
{
	int maxFlow = 0;
	while(1)
	{
		buildLevel(st);
		if(level[ed] < 0) break; // 到不了终点
		for(int x = 0; x < n; x++) iter[x] = 0; // 注意下标
		int f;
		while((f = DinicDFS(st, ed, INF)) > 0) maxFlow += f;
	}
	return maxFlow;
}

费用流

最小费用 & 最小费用最大流

基于SPFA，时间复杂度$O(F*(n+m))$，$F$是最大流总和

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
79
80
81
82
83
84
85
86
87
struct node
{
	int v, rev, cap, cost;
};

struct reNode
{
	int flow, cost;
};

int n, m;
vector <node> g[MAXN];
int dist[MAXN], prevv[MAXN], preve[MAXN];
bool vis[MAXN];

void addEdge(int u, int v, int cap, int cost)
{
	g[u].push_back((node){v, (int)g[v].size(), cap, cost});
	g[v].push_back((node){u, (int)g[u].size()-1, 0, -cost}); // 反向边
}

bool SPFA(int st, int ed)
{
	for(int x = 0; x < n; x++) dist[x] = INF, vis[x] = false; // 注意下标
	dist[st] = 0;
	queue <int> q;
	q.push(st);
	vis[st] = true;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		vis[u] = false;
		for(int x = 0; x < g[u].size(); x++)
		{
			int v = g[u][x].v, cap = g[u][x].cap, cost = g[u][x].cost;
			if(cap > 0 && dist[v] > dist[u] + cost)
			{
				dist[v] = dist[u] + cost;
				prevv[v] = u;
				preve[v] = x;
				if(!vis[v])
				{
					q.push(v);
					vis[v] = true;
				}
			}
		}
	}
	return dist[ed] < INF;
}

reNode minCostMaxFlow(int st, int ed)
{
	int flow = 0, cost = 0;
	while(SPFA(st, ed))
	{
		int f = INF;
		for(int u = ed; u != st; u = prevv[u]) f = min(f, g[prevv[u]][preve[u]].cap);
		flow += f;
		cost += f * dist[ed];
		for(int u = ed; u != st; u = prevv[u])
		{
			g[prevv[u]][preve[u]].cap -= f;
			g[u][g[prevv[u]][preve[u]].rev].cap += f;
		}
	}
	return (reNode){flow, cost};
}

int minCost(int st, int ed, int F)
{
	int flow = 0, cost = 0;
	while(F > 0 && SPFA(st, ed))
	{
		int f = F;
		for(int u = ed; u != st; u = prevv[u]) f = min(f, g[prevv[u]][preve[u]].cap);
		F -= f;
		flow += f;
		cost += f * dist[ed];
		for(int u = ed; u != st; u = prevv[u])
		{
			g[prevv[u]][preve[u]].cap -= f;
			g[u][g[prevv[u]][preve[u]].rev].cap += f;
		}
	}
	return F > 0 ? -1 : cost;
}

二分图匹配

建图：超级原点S->左边所有点->右边所有点->超级汇点T，每条边流量为1
时间复杂度$O(\sqrt{n}m)$

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
int n1, n2, S, T;

void buildBiGraph()
{
	cin >> n1 >> n2 >> m;
	n = n1 + n2 + 2;
	S = n1 + n2;
	T = S + 1;
	for(int x = 1; x <= m; x++)
	{
		int u, v;
		cin >> u >> v;
		addEdge(u, v+n1, 1);
	}
	for(int x = 0; x < n1; x++) addEdge(S, x, 1);
	for(int x = 0; x < n2; x++) addEdge(x+n1, T, 1);
}

int biMatchNum()
{
	return Dinic(S, T); // 最大匹配边数
}

struct edge
{
	int u, v;
};

vector <edge> biMatchEdge() // 基于残量网络找匹配边
{
	vector <edge> re;
	for(int u = 0; u < n1; u++)
	{
		for(int x = 0; x < g[u].size(); x++)
		{
			int v = g[u][x].v, cap = g[u][x].cap;
			if(v >= n1 && v < n1 + n2 && cap == 0) re.push_back((edge){u, v-n1});
		}
	}
	return re;
}

数据结构

线段树

ST表

树状数组

莫队

字符串

哈希函数

多项式哈希，可以将字符串映射到一个数字上，但要小心哈希冲突
$$f(s)=\sum_{i=1}^{l} {s[i] \times b^{l-i}} (\text{mod}\ M)$$

1
2
3
4
5
6
7
#define MOD 1000007 //可以根据数据范围调整
int getHash(string s, int BASE)
{
	int l = s.size(), re = 0;
	for(int x = 0; x < l; x++) re = (re*BASE+int(s[x])) % MOD;
	return re;
}

KMP

Trie字典树

AC自动机

快来参与讨论吧~

本站由 Sky Zhou 使用 Stellar 1.29.1 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
© Copyright skyzhou.top
All Rights Reserved