O(n^3) 下标需要从 1 开始

带权二分图最大完美匹配 - 任务分配问题/婚姻匹配问题 - KM (Kuhn–Munkres) 算法 注意：下面的代码是 O(n^4) 的, O(n^3) 的在后面 https://en.wikipedia.org/wiki/Assignment_problem https://en.wikiped

github.com/EndlessCheng/codeforces-go

v 与 trie 上所有数的最大异或值，trie 不能是空的 模板题 LC421 https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/ 离线 LC1707/周赛211D https://leetcode-cn

v 与 trie 上所有不超过 limit 的数的最大异或值 不存在时返回 -1 https://codeforces.com/problemset/problem/979/D LC1707/周赛211D https://leetcode-cn.com/problems/maximum-xor-wi

v 与 trie 上所有数异或不超过 limit 的最大异或值 不存在时返回 -1 原理同 countLimitXOR

团 clique 图 G 中的团和图 G 的补图中的独立集是一一对应的 图 G 中的独立集和图 G 的补图中的团是一一对应的（等价说法） https://en.wikipedia.org/wiki/Clique_(graph_theory) 最大独立集 maximal independent set

github.com/EndlessCheng/codeforces-go

* 暴搜+剪枝 根据题目的数据范围，至多只能走 $10$ 条边，这意味着爆搜的层数至多为 $10$；同时，题目保证每个节点至多有四条边与之相连，因此每次搜索时至多会递归 $4$ 次。因此计算量至多为 $4^{10}$，可以在时限内跑完。 本题的一个剪枝技巧是，先预处理起点 $0$ 到其余节点的最

最大全 1 矩形 LC85 https://leetcode-cn.com/problems/maximal-rectangle/

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

建图 + 暴力枚举所有起点 github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

Go 贪心 github.com/EndlessCheng/codeforces-go

注：题解区有 O(1) 做法 github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

* 排序+贪心 将 $\textit{cards}$ 从大到小排序，并累加前 $\textit{cnt}$ 个元素之和，记作 $\textit{sum}$，若 $\textit{sum}$ 是偶数则直接返回，若不是偶数，则我们需要从前 $\textit{cnt}$ 个元素中选一个元素 $x$，并从

github.com/EndlessCheng/codeforces-go

启发式合并：把深度小的合并到深度大的。若二者深度一样，则合并后的深度加一

注：push 一个节点就相当于 merge 这个节点

EXTRA: 线段树合并 https://www.luogu.com.cn/problem/P5494 todo 一些题目 https://www.luogu.com.cn/blog/styx-ferryman/xian-duan-shu-ge-bing-zong-ru-men-dao-fang-q

把子树 ro 合并进子树 o，返回合并前 o 的最大节点 子树 o 的所有元素比子树 ro 中的小 o != nil

github.com/EndlessCheng/codeforces-go

归并排序与逆序对 LC 面试题 51 https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/ EXTRA: LC315 https://leetcode-cn.com/problems/count-of-smaller-num

github.com/EndlessCheng/codeforces-go

若 $(a_i,b_i,c_i)$ 各部分均不超过 $(x,y,z)$，则可以执行更新操作 因此对所有满足要求的 $(a_i,b_i,c_i)$，只要各部分都出现了 $x,y,z$，最终各部分就能更新成 $x,y,z$ github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

LC 968

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

基于原始对偶方法 (primal-dual method) https://blog.xehoth.cc/DurationPlan-Primal-Dual/

最小费用流 MCFP 最小费用最大流 MCMF（即满流时的费用） 将 Edmonds-Karp 中的 BFS 改成 SPFA O(fnm) 或 Dijkstra O(fmlogn) 要求初始网络中无负权圈 性能对比（洛谷 P3381，由于数据不强所以 SPFA 很快）：SPFA 1.05s(max

github.com/EndlessCheng/codeforces-go

O(nm) 求割点

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

Kruskal 重构树 https://oi-wiki.org/graph/mst/#kruskal_1 最小生成树计数 Kirchhoff's theorem https://www.luogu.com.cn/problem/P4208 todo 最小差值生成树 edges 中的节点编号从 0 开

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

* 从前往后匹配+从后往前匹配 如果去掉第一种操作，由于交替字符串只有 $\texttt{1}$ 开头与 $\texttt{0}$ 开头两种，我们只需要检查 $s$ 与 $\texttt{1010}\cdots$ 和 $\texttt{0101}\cdots$ 中哪个不同字母最少，这样第二种操作次

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

github.com/EndlessCheng/codeforces-go

马走日从 (0,0) 到 (x,y) 所需最小步数 无边界 LC1197/双周赛9B https://leetcode-cn.com/contest/biweekly-contest-9/problems/minimum-knight-moves/ 有边界+打印方案 https://www.acwi

github.com/EndlessCheng/codeforces-go

均分纸牌 https://www.luogu.com.cn/problem/P1031 环形 https://www.luogu.com.cn/problem/P2512 https://www.luogu.com.cn/problem/P3051 https://www.luogu.com.cn/

github.com/EndlessCheng/codeforces-go

* 排序+贪心 由于座位和学生数相同，一个萝卜一个坑，将座位和学生位置排序后，第 $i$ 个学生可以对应第 $i$ 个座位。 由于交换任意两个学生对应的座位不会产生更少的移动次数（可以画一画，证明略），所以上述对应关系可以产生最少移动次数，累加位置之差即为答案。 */ github.com/E

倒序思想 来源自被删除的 C 题 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45798625 有一个大小为 n*m 的网格图，和一个长为 n*m 的目标位置列表，每个位置表示网格图中的一个格点且互不相同 网格图初