全面的算法代码仓库
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.gitignore 添加.gitignore文件 Dec 11, 2016
2-Satisfiability.cpp 2-SAT可满足性问题(附POJ - 3678 Katu Puzzle代码) Feb 9, 2017
Aho-Corasick-Automaton.cpp 更正文件名单词拼写的错误 Feb 17, 2017
Bellman-Ford(Queue-Optimised).cpp 队列优化的Bellman-Ford算法(SPFA算法) Aug 29, 2016
Bellman-Ford.cpp 单源最短路径(Bellman-Ford算法) Aug 14, 2016
Biconnected-Component.cpp 双连通分量(未验证正确性) Dec 14, 2016
Bigraph-Matching(Edmonds-Karp).cpp 利用Edmonds-Karp算法进行二分图匹配(附CodeVS - 2390 填报志愿代码) Nov 23, 2016
Bigraph-Matching(Improved-Shortest-Augmenting-Path).cpp 使用ISAP算法进行二分图匹配(附UOJ - 78 二分图最大匹配代码) Feb 11, 2017
Binary-Search-Tree.cpp 普通的二叉搜索树 Oct 22, 2016
Breadth-First-Search.cpp 重命名文件 Aug 7, 2016
Bubble-Sort.cpp 冒泡排序 Aug 12, 2016
Bucket-Sort.cpp 桶排序 Sep 10, 2016
Cartesian-Tree.cpp 笛卡尔树的构建 Jul 6, 2017
Centre-of-Gravity(Polygon).cpp 求任意多边形重心(附HDU - 1115 Lifting the Stone代码) Feb 13, 2017
Combination(Recursion).cpp 递推法计算组合数 Nov 27, 2016
Combination.cpp 枚举组合 Aug 27, 2016
Complex-Number.cpp 修正错误的复数乘法 Jan 13, 2017
Cut-Vertex.cpp 割点(附CodeVS - 5524 割点代码) Nov 21, 2016
Depth-First-Search.cpp 重命名文件 Aug 7, 2016
Dijkstra(Heap-Optimised).cpp 更正heap_float函数的错误 Feb 23, 2017
Dinic.cpp 最大流Dinic算法 Mar 3, 2017
Disjoint-Set-Union.cpp 并查集(附CodeVS - 1073 家族代码) Aug 5, 2016
Edmonds-Karp.cpp 最大流Edmonds-Karp算法(附CodeVS - 1993草地排水代码) Aug 17, 2016
Euler's-Totient-Function-Sieve(Linear).cpp 欧拉函数的线性筛法 Jan 13, 2017
Euler's-Totient-Function.cpp 欧拉函数(附CodeVS - 4939 欧拉函数代码) Oct 9, 2016
Eulerian-Tour(Digraph).cpp 有向图的欧拉回路 Nov 17, 2016
Extended-Euclid.cpp 拓展欧几里德算法 Aug 10, 2016
Fast-Exponentiation.cpp 简单的快速幂 Aug 19, 2016
Fast-Fourier-Transform(Iterative).cpp 快速傅立叶变换的迭代实现(附UOJ - 34 多项式乘法代码) Jun 20, 2018
Fast-Number-Theoretic-Transform.cpp 使用数论进行快速傅立叶变换(快速数论变换)(附UOJ - 34 多项式乘法代码) Jan 13, 2017
Fenwick-Tree.cpp 树状数组(附CodeVS - 3900 区间和值代码) Aug 15, 2016
Fibonacci-Heap.cpp 支持插入和抽取最小元素的斐波那契堆 May 18, 2017
Floyd-Warshall.cpp Floyd算法(附CodeVS - 1077 多源最短路代码) Sep 17, 2016
Gaussian-Elimination.cpp 高斯消元(附BZOJ - 1013 球形空间产生器代码) Jan 16, 2017
Graham-Scan.cpp Graham扫描法求凸包(附CodeVS - 1298 凸包周长代码) Oct 4, 2016
Greatest-Common-Divisor.cpp 解决了一数为0时除以0的错误 Aug 11, 2016
Heap-Sort.cpp 堆排序 Oct 22, 2016
Heavy-Light-Decomposition.cpp 添加例题:BZOJ - 1036 树的统计 Jan 4, 2017
High-Precision(Integer).cpp 改进构造函数,使其能够声明多维数组 Dec 27, 2016
Hungarian-Algorithm.cpp 匈牙利算法(附UOJ - 78 二分图最大匹配代码) Mar 18, 2017
Improved-Shortest-Augmenting-Path(Gap-Optimised).cpp 加入gap优化的ISAP算法(附CodeVS - 1993 草地排水代码) Jan 23, 2017
Improved-Shortest-Augmenting-Path(Naive).cpp 未加优化的ISAP算法 Nov 23, 2016
Insertion-Sort.cpp 插入排序 Nov 21, 2016
K-Dimensional-Tree.cpp KD-Tree May 23, 2017
Knuth-Morris-Pratt.cpp 字符串匹配Knuth-Morris-Pratt算法 Aug 5, 2016
Kruskal.cpp Kruskal算法求最小生成树 Oct 4, 2016
Least-Common-Ancestor(Tarjan).cpp 删除了两句无效代码 Aug 8, 2016
Leftist-Tree.cpp 左偏树的基本操作 Jan 20, 2017
Linear-Basis.cpp 线性基(用于解决异或和问题) Mar 5, 2017
Link-Cut-Tree(with-Reverse).cpp 带翻转操作的LCT(LCT维护森林)(附BZOJ - 2049 洞穴勘测代码) Mar 17, 2017
Link-Cut-Tree.cpp Link-Cut-Tree(附BZOJ - 2002 弹飞绵羊代码) Feb 26, 2017
Longest-Common-Substring.cpp 最长公共子串(附CodeVS - 3160 最长公共子串代码) Nov 27, 2016
Longest-Increasing-Subsequence(n·log(n)).cpp 最长上升子序列(n·log(n)) Oct 18, 2016
Lowest-Common-Ancestor(Doubling).cpp 倍增法求最近公共祖先 Nov 16, 2016
Matrix-Multiplication(Naive).cpp 朴素的矩阵乘法 Aug 17, 2016
Merge-Sort.cpp Add files via upload Aug 4, 2016
Miller-Rabin.cpp Miller-Rabin素数测试 Apr 14, 2017
Min-Heap.cpp 修正了堆插入操作的错误 Jan 24, 2017
Modular-Multiplicative-Inverse-Sieve(Factorial,Linear).cpp 线性时间预处理[1,n]阶乘的逆元 Feb 10, 2017
Modular-Multiplicative-Inverse-Sieve(Linear).cpp 使用递推式线性求解乘法逆元 Jan 13, 2017
Modular-Multiplicative-Inverse.cpp 重命名文件 Aug 11, 2016
Non-Rotating-Treap.cpp 无旋式Treap Jul 8, 2017
Palindromic-Tree.cpp 回文树/回文自动机 Apr 8, 2017
Permutation.cpp 枚举全排列 Dec 12, 2016
Persistent-Array.cpp 可持久化数组 Dec 26, 2016
Persistent-Segment-Tree(Sum).cpp 仅支持单点修改的可持久化线段树(未验证正确性) Dec 3, 2016
Persistent-Treap.cpp 不支持删除的可持久化Treap Dec 18, 2016
Persistent-Trie.cpp 可持久化字典树(附BZOJ - 4477 字符串树代码) Jun 1, 2017
Prim.cpp 最小生成树Prim算法 Jul 15, 2017
Prime-Check(Naive).cpp 朴素的质数测试(O(sqrt(n))) Nov 24, 2016
Prime-Sieve(Linear).cpp 更新素数线性筛法的代码 Jan 13, 2017
Primitive-Root.cpp 求解原根 Jan 19, 2017
Prüfer-Sequence(Tree-to-Sequence).cpp 将树转化为Prüfer序列 Mar 29, 2017
Queue.cpp 队列的基本操作 Oct 5, 2016
Quick-Sort(Extra-Optimised).cpp 修正了随机化部分以及循环的错误 Oct 5, 2016
Quick-Sort(Randomized).cpp 快速排序的随机化版本 Oct 5, 2016
Quick-Sort.cpp 修正了错误的函数类型 Sep 10, 2016
Radix-Sort.cpp 简化代码,提升运行效率 Nov 24, 2016
Reverse-Pair(Merge-Sort).cpp 使用归并排序求解逆序对 Dec 16, 2016
Segment-Direction.cpp 求两个有向线段的时针关系 Sep 24, 2016
Segment-Intersection.cpp 判断两条线段是否有交点(附HDU - 1086 You can Solve a Geometry Problem too代码) Dec 26, 2016
Segment-Tree(Minimum).cpp 更正错误的线段树操作 Nov 4, 2016
Segment-Tree(Sum).cpp 线段树维护区间和(附CodeVS - 1082 线段树练习3代码) Sep 11, 2016
Selection.cpp 普通的选择算法(序列第k小元素) Nov 20, 2016
Shell-Sort.cpp 希尔排序 Oct 21, 2017
Sieve-of-Eratosthenes.cpp Eratosthenes素数筛法 Nov 12, 2016
Singly-Linked-List(Pointer).cpp 单向链表的基本操作(指针版) Nov 28, 2016
Skip-List.cpp 跳表(附带调试函数,未验证正确性) Dec 1, 2016
Sparse-Table.cpp 删除未引用的头文件 Nov 11, 2016
Splay(Single-Rotation).cpp 单旋版本的伸展树 Dec 13, 2016
Splay-with-Parent(Array).cpp 维护父亲的Splay(未完善) Feb 22, 2017
Splay.cpp 修正了错误的伸展操作并简化代码 Dec 15, 2016
Sprague-Grundy.cpp 博弈论SG函数(附HDU - 1536 S-Nim代码) Dec 4, 2016
Stack.cpp 栈的基本操作 Aug 26, 2016
Stirling-Number(Cycle,Unsigned,Recursion).cpp 递推法求解无符号第一类斯特林数(圆排列) Dec 11, 2016
Stirling-Number(Subset,Recursion).cpp 递推法求解第二类斯特林数(子集合) Dec 11, 2016
Suffix-Array(Doubling).cpp 优化运行效率 Nov 25, 2016
Suffix-Array-with-Height(Doubling).cpp 附带Height数组的后缀数组(附UOJ - 35 后缀排序代码) Nov 27, 2016
Suffix-Automaton.cpp 后缀自动机(未验证正确性) Feb 17, 2017
Tarjan(Strongly-Connected-Components).cpp Tarjan算法求强连通分量 Oct 28, 2016
Treap.cpp 不支持删除的Treap Dec 17, 2016
Trie(Array).cpp 更改文件名 Nov 29, 2016
Trie(Pointer).cpp 指针版的Trie树(以小写字母字符串为例) Nov 30, 2016
license.md 创建许可证 Oct 23, 2016
readme.md 修订readme;修改对于Pull Request态度的表述 Oct 28, 2017

readme.md

Algorithms

  这里有各种算法的C++代码,任何人可以在自己的任何程序中使用。欢迎大家指出代码中的错误以及有待改进的地方。

  本仓库内所有代码的授权方式为The Unlicense。大家如果使用我的代码开发自己的软件挣了大钱,或是参考我的代码在信息学奥林匹克竞赛中获得金牌,我都会很高兴的。使用这里的代码之后,你可以自主选择是否公开源代码。总而言之,你可以把这里的代码当作你自己写的一样,无论怎样使用都是被允许的。但是,我不对本仓库内代码的正确性负责。大家要是使用我的代码开发软件而导致程序崩溃,或是参考我的代码在考试时出错,请不要向我抱怨。如果你愿意,遇到问题可以在Issues中提出来,我们共同解决。

  本仓库有两个分支,master和candidate。master用于存放原作者自己编写的代码,candidate接受所有合理的Pull Request。

  以下索引提供了本仓库内算法的中文名,方便大家查找。此列表更新可能有较长时间的延迟,不保证所有已提交算法的名称都在列表中出现。

Index

--------------------------Contents-------------------------- --------------------------FileName--------------------------
AC自动机 Aho-Corasick-Automation
单源最短路径(SPFA) Bellman-Ford(Queue-Optimised)
单源最短路径(Bellman-Ford) Bellman-Ford
使用Edmonds-Karp进行二分图匹配 Bigrpah-Matching(Edmonds-Karp)
普通的二叉搜索树 Binary-Search-Tree
广度优先搜索 Breadth-First-Search
冒泡排序 Bubble-Sort
桶排序 Bucket-Sort
组合数的递推求解 Combination(Recursion)
枚举组合 Combination
基本的复数类 Complex-Number
割点 Cut-Vertex
深度优先搜索 Depth-First-Search
堆优化的Dijkstra算法 Dijkstra(Heap-Optimised)
并查集 Disjoint-Set-Union
最大流Edmonds-Karp算法 Edmonds-Karp
欧拉函数 Euler's-Totient-Function
有向图的欧拉回路 Eulerian-Tour(Digraph)
拓展欧几里得算法 Extended-Euclid
简单的快速幂 Fast-Exponentiation
树状数组 Fenwick-Tree
所有结点对之间的最短路径(Floyd) Floyd-Warshall
凸包算法(Graham扫描法) Graham-Scan
辗转相除法求最大公约数 Greatest-Common-Divisor
堆排序 Heap-Sort
ISAP算法 Improved-Shortest-Augmenting-Path(Naive)
插入排序 Insertion-Sort
字符串匹配(KMP) Knuth-Morris-Pratt
最小生成树(Kruskal) Kruskal
最近公共祖先(Tarjan) Least-Common-Ancestor(Tarjan)
使用后缀数组求解最长公共子串 Longest-Common-Substring
最长上升子序列(n·log(n)) Longest-Increasing-Subsequence(n·log(n))
倍增法求最近公共祖先 Lowest-Common-Ancestor(Doubling)
朴素的矩阵乘法 Matrix-Multiplication(Naive)
归并排序 Merge-Sort
最小堆 Min-Heap
乘法逆元 Modular-Multiplicative-Inverse
仅支持单点修改的可持久化线段树(维护区间和值) Persistent-Segment-Tree(Sum)
试除法素数测试 Prime-Check(Naive)
线性的素数筛法 Prime-Sieve(Linear)
队列的基本操作 Queue
快速排序的优化版本 Quick-Sort(Extra-Optimised)
快速排序的随机化版本 Quick-Sort(Randomized)
快速排序 Quick-Sort
使用向量叉积判断两个有向线段的时针关系 Segment-Direction
线段树维护区间最大值 Segment-Tree(Maximum)
线段树维护区间最小值 Segment-Tree(Minimum)
线段树维护区间和值 Segment-Tree(Sum)
普通的选择算法 Selection
Eratosthenes素数筛法 Sieve-of-Erotosthenes
指针版的单向链表 Singly-Linked-List(Pointer)
跳表 Skip-List
ST表 Sparse-Table
伸展树 Splay
博弈论SG函数 Sprague-Grundy
栈的基本操作 Stack
递推法求解无符号第一类斯特林数 Stirling-Number(Cycle,Unsigned,Recursion)
递推法求解第二类斯特林数 Stirling-Number(Subset,Recursion)
倍增法求解后缀数组 Suffix-Array(Doubling)
倍增法求解后缀数组(附带Height数组) Suffix-Array-with-Height(Doubling)
使用Tarjan算法求解强连通分量 Tarjan(Strongly-Connected-Components)
数组版的字典树 Trie(Array)
指针版的字典树 Trie(Pointer)