ACM CS 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; 
}

像我这种喜欢用cin/cout的，建议补上这个关闭流同步：

1
2
cin.tie(nullptr);
ios::sync_with_stdio(false);

二分答案

最基础最重要的算法之一
实际使用主要需要设计二分条件，即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 \bmod 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);
}

（其实STL有函数__gcd(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;

CRT 中国剩余定理

用于解以下一元线性同余方程组
$$
\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;
}

线性代数

矩阵快速幂

给定一个 $n \times n$ 的矩阵 $A$，还有次数 $k$ ，能快速算出 $A^k \bmod M$ ，时间复杂度 $O(n^3 \log k)$ ，适合用于加速 $n$ 比较小，但次数 $k$ 比较大的矩阵幂运算，经常用于优化递推DP式子

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
const LL MOD = 1e9+7;

// re = i * j (Matrix)
void matrixTimes(LL i[MAXN][MAXN], LL j[MAXN][MAXN], LL re[MAXN][MAXN], int n)
{
    LL a[MAXN][MAXN] = {};
    for(int x = 1; x <= n; x++)
        for(int y = 1; y <= n; y++)
            for(int z = 1; z <= n; z++)
                a[x][y] = (a[x][y] + (i[x][z] * j[z][y]) % MOD) % MOD;
    for(int x = 1; x <= n; x++)
        for(int y = 1; y <= n; y++) re[x][y] = a[x][y];
}

void matrixFastPow(LL A[MAXN][MAXN], int n, LL k)
{
    LL I[MAXN][MAXN] = {};
    for(int x = 1; x <= n; x++) I[x][x] = 1;
    while(k > 0)
    {
        if(k & 1) matrixTimes(I, A, I, n);
        matrixTimes(A, A, A, n);
        k >>= 1;
    }
    for(int x = 1; x <= n; x++)
        for(int y = 1; y <= n; y++) A[x][y] = I[x][y];
}

高斯消元

解 $n$ 元一次线性方程组，时间复杂度 $O(n^3)$

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
int n;
double a[MAXN][MAXN], b[MAXN];
double ans[MAXN];

// -1: 无解，0: 无穷解，1: 唯一解
int Gauss() {
    for (int i = 1; i <= n; i++) a[i][n + 1] = b[i];
    int r = 1;
    for(int c = 1; c <= n; c++) {
        int t = r;
        for(int i = r; i <= n; i++)
            if(fabs(a[i][c]) > fabs(a[t][c])) t = i;
        if(fabs(a[t][c]) < eps) continue;
        for(int j = c; j <= n + 1; j++) swap(a[t][j], a[r][j]);
        for(int j = n + 1; j >= c; j--) a[r][j] /= a[r][c];
        for(int i = r + 1; i <= n; i++)
            if (fabs(a[i][c]) > eps)
                for (int j = n + 1; j >= c; j--) a[i][j] -= a[r][j] * a[i][c];
        r++;
    }
    for(int i = r; i <= n; i++) {
        bool allZero = true;
        for(int j = 1; j <= n; j++)
            if (fabs(a[i][j]) > eps) { allZero = false; break; }
        if(allZero && fabs(a[i][n + 1]) > eps) return -1;
    }
    if(r > n) {
        for(int i = n; i >= 1; i--) {
            ans[i] = a[i][n + 1];
            for (int j = i + 1; j <= n; j++) ans[i] -= a[i][j] * ans[j];
        }
        return 1;
    }
    return 0;
}

斐波那契数（递归数）与卡特兰数

递归数

考虑非负整数 $n$ 上的递归关系：
$$
F_n =
\begin{cases}
f_0 & \text{if } n = 0 \\
f_1 & \text{if } n = 1 \\
a \cdot F_{n-1} + b \cdot F_{n-2} & \text{otherwise}
\end{cases}
$$

可以得到通项公式：
$$
F_n = \frac{k^n(f_1 - m f_0) - m^n(f_1 - k f_0)}{k-m} \\
\\
m, k = \frac{a \pm \sqrt{a^2+4b}}{2}
$$

卡特兰数

常用于二叉树、括号匹配、多边形三角划分等问题

$$
\begin{align}
f_n &= \sum_{i=0}^{n-1}f_i \cdot f_{n-i+1} \\
&= \frac{C_{2n}^n}{n+1} \\
&= C_{2n}^n - C_{2n}^{n-1}
\end{align}
$$

素数相关

质因数分解

能在 $O(\sqrt{n})$ 的时间复杂度下求出 $n$ 的质因数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Factorize(LL n, vector<int> &factors, map<int,int> &primeCnt)
{
    for(LL i = 2; i * i <= n; i++)
	{
        if(n % i == 0)
		{
            factors.push_back((int)i);
            while (n % i == 0)
			{
                primeCnt[(int)i]++;
                n /= i;
            }
        }
    }
    if(n > 1)
	{
        factors.push_back((int)n);
        primeCnt[(int)n]++;
    }
}

欧拉线性筛素数

能在 $O(n)$ 的时间复杂度下快速筛出 $1$ 到 $n$ 的所有素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isPrime[MAXN];
int Prime[MAXN];

void EulerPrime(int n) // 筛到 n
{
    int cnt = 0;
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = 0;
    for(int x = 2; x <= n; x++)
    {
        if(isPrime[x]) Prime[++cnt] = x;
        for(int y = 1; y <= cnt && x*Prime[y] <= n; y++)
        {
            isPrime[x*Prime[y]] = false;
            if(x % Prime[y] == 0) break;
        }
    }
}

威尔逊定理

$p$ 为素数 $\Leftrightarrow (p-1)! \equiv -1 \pmod p$

费马小定理

若 $p$ 为素数，则：
$$
a^p \equiv a \pmod p
$$

特殊形式：

若 $p$ 为素数，$a$ 为正整数，且 $a$ 和 $p$ 互质，则：
$$
a^{p-1} \equiv 1 \pmod p
$$

欧拉函数和定理

欧拉函数：对于正整数 $n$，欧拉函数 $\phi(n)$ 是小于等于 $n$ 中与 $n$ 互质的数的数目，计算公式：

$$
\phi(n) = n \prod_{i=1}^k (1-\frac{1}{p_i})
$$

其中，$p_i$ 是 $n$ 的质因子，而且只计算一次

前置定理：

  • 若 $p$ 为素数，则：$\phi(p) = p-1$
  • 若 $p$ 为素数，其幂次 $p^a$，则：$\phi(p^a) = (p-1) \cdot p^{a-1}$
  • 若 $a$ 与 $b$ 互质，则：$\phi(ab) = \phi(a) \cdot \phi(b)$

欧拉定理：

若 $a$ 与 $m$ 互质，则:

$$
a^{\phi(m)} \equiv 1 \pmod m
$$

可以在 $O(n)$ 的时间复杂度下算出 $\phi(1)$ 到 $\phi(n)$，也可以用 $O(\sqrt{n})$ 的复杂度单次算出 $\phi(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
int phi[MAXN], prime[MAXN];
bool isComposite[MAXN];
int tot = 0;

void EulerFunctionAll(int n) // 算 1 到 n
{
    phi[1] = 1;
    for(int x = 2; x <= n; x++)
    {
        if(!isComposite[x])
        {
            prime[tot++] = x;
            phi[x] = x - 1; // 质数：φ(p)=p-1
        }
        for(int y = 0; y < tot && 1LL * x * prime[y] <= n; y++)
        {
            int p = prime[y];
            isComposite[x * p] = true;
            if (x % p == 0)
            {
                phi[x * p] = phi[x] * p;
                break;
            }
            else phi[x * p] = phi[x] * (p - 1);
        }
    }
} // 结果存在 phi 数组里

int EulerFunction(int n) // 单次计算
{
    int re = n;
    for(int x = 2; x*x <= n; x++)
    {
        if(n % x == 0)
        {
            re = re / x * (x-1);
            while(n % x == 0) n /= x;
        }
    }
    if(n > 1) re = re / n * (n-1);
    return re;
}

莫比乌斯反演

给定函数 $F(n)$ 和 $f(n)$ 定义在非负整数集合上，并满足条件：
$$
F(n) = \sum_{d|n} f(d)
$$
则有结论：
$$
f(n) = \sum_{d|n}\mu(d)F\left(\frac{n}{d}\right)
$$

其中，莫比乌斯函数
$$
\mu(n) =
\begin{cases}
1 & n = 1 \\
0 & n\text{ 含有平方因子} \\
(-1)^k & k\text{ 是 }n\text{ 不同的质因子个数}
\end{cases}
$$
也就是说，$n>1$ 的时候，如果能分解成 $k$ 个不同的质因数直接相乘，那么函数值为 $(-1)^k$，否则为 $0$。比如 $\mu(10) = 1$，$\mu(12) = 0$
其有两个性质：

  1. 对于任意正整数 $n$ 有：$\sum_{d|n} \mu(d) = \begin{cases}1 & n = 1 \\ 0 & n > 1\end{cases}$
  2. 对于任意正整数 $n$ 有：$\sum_{d|n} \frac{\mu(d)}{d} = \frac{\phi(n)}{n}$

可以在 $O(n)$ 的时间复杂度下算出 $\mu(1)$ 到 $\mu(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
bool vis[MAXN];
int mu[MAXN], prime[MAXN];

void MobiusFunctionAll(int n)
{
    mu[1] = 1;
    int cnt = 0;
    for(int x = 2; x < n; x++)
    {
        if(!vis[x])
        {
            prime[cnt++] = x;
            mu[x] = -1;
        }
        for(int y = 0; y < cnt && x*prime[y] < n; y++)
        {
            vis[x*prime[y]] = true;
            if(x % prime[y]) mu[x*prime[y]] = -mu[x];
            else
            {
                mu[x*prime[y]] = 0;
                break;
            }
        }
    }
}

FFT 快速傅里叶变换

给定一个 $n$ 次多项式 $F(x)$ ，和一个 $m$ 次多项式 $G(x)$ ，FFT能快速求出 $F(x) \times G(x)$

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
int n, m;
complex <double> a[MAXN], b[MAXN];
int l, r[MAXN], ans[MAXN];
int limit = 1;

void FFT(complex <double> *A, int type)
{
    for(int i = 0; i < limit; i++) 
        if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid <<= 1)
    {
        complex <double> Wn(cos(Pi/mid), type*sin(Pi/mid));
        for(int R = mid<<1, j = 0; j < limit; j += R)
        {
            complex <double> w(1, 0);
            for(int k = 0; k < mid; k++, w = w*Wn)
            {
                complex <double> x = A[j+k], y = w*A[j+mid+k];
                A[j+k] = x + y;
                A[j+mid+k] = x - y;
            }
        }
    }
}

void doFFT()
{
	while(limit <= n + m) limit <<= 1, l++;
	for(int i = 0; i < limit; i++) r[i] = (r[i>>1]>>1)|((i&1)<<(l-1)) ;
	FFT(a,1); FFT(b,1);
	for(int i = 0; i <= limit; i++) a[i] = a[i] * b[i];
	FFT(a,-1);
	for(int i = 0; i <= n + m; i++) ans[i] = (int)(a[i].real()/limit + 0.5);
}
// 输入 a 和 b 数组，doFFT()之后能得到 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);
                }
            }
        }
    }
}

Dijkstra

有向/无向图单源最短路，能求出st到任意一个点的最短路（无负环），加上小根堆优化后时间复杂度 $O(m \log 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
55
56
struct node
{
	int v, dis;
};

struct pri
{
	int ans, id;
	bool operator < (const pri &x) const{return x.ans < ans;}
};

priority_queue <pri> q;
vector <node> g[MAXN];
int n, m, d[MAXN], pre[MAXN];
bool vis[MAXN];

void Dijkstra(int st)
{
	for(int x = 1; x <= n; x++)
    {
        d[x] = INF;
        pre[x] = -1;
        vis[x] = false;
    }
	d[st] = 0;
	q.push((pri){0, st});
	while(!q.empty())
	{
		pri tmp = q.top();
		q.pop();
		int u = tmp.id;
		if(!vis[u])
		{
			vis[u] = true;
			for(int y = 0; y < g[u].size(); y++)
			{
				int v = g[u][y].v;
				if(!vis[v] && d[u] + g[u][y].dis < d[v])
				{
					d[v] = d[u] + g[u][y].dis;
                    pre[v] = u;
                    q.push((pri){d[v], v});
				}
			}
		}
	}
}

void printPath(int ed) // 从ed回溯
{
    vector <int> ans;
    for(int u = ed; u != -1; u = pre[u]) ans.push_back(u);
    reverse(ans.begin(), ans.end());
    for(int u : ans) cout << u << " ";
    cout << endl;
}

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 \rightarrow 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