s-t 最小割 最小割问题可以形象地理解为：为了不让水从 s 流向 t，怎么破坏水沟代价最小？被破坏的水沟必然是从 s 到 t 的单向水沟。而在有向图流网络 G = (V，E) 中，割把图分成 S 和 T = V - S 两部分，源点 s ∈ S，汇点 t ∈ T，这称为 s - t 割。最大流最小割定理：源点 s 和 汇点 t 之间的最小割等于 s 和 t 之间的最大流。需要注意的是，定理中的最大流是指流量，而最小割是指容量。全局最小割：把 s-t 最小割问题扩展到全局，有全局最小割问题。 问题一，是否存在一个最小割，其中该边被割？ 对于一条边的两个端点 u， v，若该边存在一个最小割中...

最小费用最大流 假设每条边除了有一个容量限制外，还有一个单位流量所需的费用(cost)。该网络中花费最小的最大流称为最小费用最大流，即总流量最大的情况下，总费用最小的流。 证：在残余网络上求最短路是最小费用 设有 f 为以以上方式求出的结果， 设 f ’ 和 f 流量相同，但是费用更少因为 f ‘ - f 的流量流入流出为 0，所以他是成环的又因为 f ’ - f 的费用是负的，所以在这些环中，存在负环 结论：f 是最小费用流的充要条件是残余网络中没有负环 对于流量为 0 的流 f [ 0 ] ，其残余网络为原图，原图没有负环，则 f [ 0 ] 就是最小费用流设流量为 i 的...

概述 我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。最大流算法有很多种，基本上分为两类：1.“增广路”算法。例如 Edmonds-Karp 算法、Dinic 算法、ISAP 算法。2.“预流推进”算法。例如 Ford-Fulkerson 增广路方法 残留网络：迭代后残留容量所产生的图，每次新的迭代在上一次的残留网络上进行。 增广路：在残留网络上找到一条从 s 到 t 的路径。 Ford-Fulkerson 方法的运行时间依赖于增广路径的搜索次数。虽然用 BFS 或者 DFS 都行，但是 DFS 这种深度搜索模式可能陷入长时间的迭代，但如果用 B...

#AC自动机 时间复杂度： AC自动机是多模匹配算法，能在一个文本串中同时查找多个不同的模式串。 注： “fail指针” 、 “蓝色虚点” #include<bits/stdc++.h> using namespace std; const int maxn = 4e5+1; // 匹配串的总长度 int tree[maxn][26], tot, fail[maxn]; int id[maxn], dep[maxn], en[maxn], sz[maxn][2]; void build(int x, string t) { int pos = 0, m = t...

定义 定义两个数论函数 f，g 的 Dirichlet 卷积为： 性质 Dirichlet 卷积满足以下运算规律： 交换律 结合律 分配率 ，其中 为 Dirichlet 卷积的单位元（任何函数卷 都为其本身）

积性函数： 若函数 满足 且 ， 都有 ，则 为积性函数。 完全积性函数： 若函数 满足 且 都有 ，则 为完全积性函数。 性质 若 和 均为积性函数，则以下函数也为积性函数： 设 若 为积性函数，则有 若 为完全积性函数，则有 例子 积性函数 欧拉函数：莫比乌斯函数： 完全积性函数 单位函数：

莫比乌斯反演 和 是定义在非负整数集合上的两个函数，并且满足条件 。那么，我们得到结论：证： 莫比乌斯函数 在上面的公式中有一个莫比乌斯函数 ，它的定义如下： 若 ，那么 若 ， 均为互异素数，那么 其他情况下 性质 对于 函数，它有如下的常见性质： 设 表示 n 的质因子个数， 对任意正整数 n 有： 证： 对任意正整数 n 有： 证： 用线性筛选求莫比乌斯反演函数的代码： int init(int n) { int tot = 0; for(int i = 1; i <= n; ++ i) vis[i] = 0;...

排列：组合：这里把组合数 用符号 表示，称为二项式系数。 杨辉三角（国外称帕斯卡三角）是二项式系数 的典型应用。每一行从上一行推导而来。复杂度 观察 的展开： 每一行展开的系数刚好对应杨辉三角每一行的数字。也就是说杨辉三角可以用 来定义和计算。二项式系数： ，也就是杨辉三角中第 n 行，第 k 个数。二项式定理： ，n = 30， 30！ 超过了 long long 的范围，此时可以利用 和 的递推关系 逐个推导，避免计算阶乘。

素数：一个数 n ，若不能在[2,n-1]中找到一个能整除 n 的数 d ，则 n 为素数。 试除法判断素数 时间复杂度： bool is_prime(int n) { if (n <= 1) return false; for(int i = 2; i * i <= n; ++ i) { if (n % i == 0) return false; } return true; }埃氏筛法 时间复杂度：原理：每次筛出一个素数 x，并把 x 的倍数筛出。注：对于 [ 2 * i，i * i ] 之间的合数会被比 i 更小的素数筛去，...

二分图匹配 二分图：把无向图 G = （V，E）分为两个集合 V1，V2，所有的边都在 V1 和 V2 之间，而 V1 或 V2 的内部没有边。V1 中的一个点与 V2 中的一个点关联，称为匹配。染色法：一个图是否为二分图，一般用“染色法”进行判断。用两种颜色对所有顶点进行染色，要求一条边所连接的两个相邻顶点的颜色不相同。染色结束后，如果所有相邻顶点的颜色都不相同，它就是二分图。结论：一个图是二分图，当且仅当它不含边的数量为奇数的圈。 二分图最大匹配问题 二分图最大匹配问题：无权图，求包含边数最多的匹配，即二分图的最大匹配。 匈牙利算法 时间复杂度: 匈牙利算法可以看成最大流的一个特殊实现...

#pragma GCC optimize(3, "Ofast", "inline") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #include<cstdio> #include<cstring> #include<iostream> using namespace std; typedef long long LL; const int base = 1e8; co...

状态压缩dp的概念 状压 dp 是动态规划的一种，通过将状态压缩为二进制数来处理复杂的集合问题。 方案数 例题： 农夫有一块长方形土地，化成 n 行 m 列的方格。他准备种玉米，养牛（在一个格子内），不过有些格子很贫瘠，不适合种玉米。还有，牛不喜欢在一起吃，所以牛不能放在相邻的格子里，给出这块地的情况求出农夫有多少种种玉米的方案。所有方格都不种玉米也算一种方案。解决： 时间复杂度 用 dp[i][j] 表示第 i 行采取编号为 j 的方案时前 i 行可以得到的可行方案总数。从第 i-1 行转移到第 i 行的状态转移方程：把最后一行的相加就得到了答案： // poj 3254（http...

逆元 方程 的一个解 x ，称 x 为 a 模 M 的逆。 扩展欧几里得求解逆元 注：a 和 M 需要互质，速度比费马小定理快一点 void exgcd(int a, int b, int &x, int &y) { // ax + by = gcd(a,b) if (b == 0) x = 1, y = 0; else exgcd(b, a%b, y, x), y -= a/b*x; } void inv(int a, int M) { // 逆元 int x, y; exgcd(a, M, x, y); return (x%M...

数的各位数之和 一个数 x 在 （x*i+1）进制下，对于任意一个能被 x 整除的数，它的各位之和也能被 x 整除。例如：十进制下的 3。 数的拆分 数 x 拆成 n 个相等的数，使 n 个数之积最大。 （n 为个数限制）例如： 数 x 拆成 3 和 2，使拆分出的数之积最大。（个数没有限制）例如： ，