ACMICPC代码库大全：图论、网络流、数据结构、数论、计算几何等

ACMICPC代码库 本资源库由吉林大学计算机科学与技术学院2005级学生创建，旨在提供一个涵盖广泛的算法和数据结构库，供 ACM/ICPC 竞赛选手和计算机科学爱好者参考和学习。 **Graph 图论** * DAG 的深度优先搜索标记 * 无向图找桥 * 无向图连通度（割） * 最大团问题 DP + DFS * 欧拉路径 O(E) * DIJKSTRA 数组实现 O（N^2） * DIJKSTRA O(E\*LOGE) * BELLMANFORD 单源最短路 O(VE) * SPFA(SHORTEST PATH FASTER ALGORITHM) * 第 K 短路（DIJKSTRA） * 第 K 短路（A\*） * PRIM 求 MST * 次小生成树 O(V^2) * 最小生成森林问题(K 颗树) O(MLOGM) * 有向图最小树形图 * MINIMAL STEINER TREE * TARJAN 强连通分量 * 弦图判断 * 弦图的 PERFECT ELIMINATION 点排列 * 稳定婚姻问题 O(N^2) * 拓扑排序 * 无向图连通分支(DFS/BFS 邻接阵) * 有向图强连通分支(DFS/BFS 邻接阵) O(N^2) * 有向图最小点基(邻接阵) O(N^2) * FLOYD 求最小环 * 2-SAT 问题 **Network 网络流** * 二分图匹配（匈牙利算法 DFS 实现） * 二分图匹配（匈牙利算法 BFS 实现） * 二分图匹配（HOPCROFT－CARP 的算法） * 二分图最佳匹配（KUHN MUNKRAS 算法 O(M*M*N)） * 无向图最小割 O(N^3) * 有上下界的最小（最大）流 * DINIC 最大流 O(V^2 \* E) * HLPP 最大流 O(V^3) * 最小费用流 O(V \* E \* F) * 最小费用流 O(V^2 \* F) * 最佳边割集 * 最佳点割集 * 最小边割集 * 最小点割集（点连通度） * 最小路径覆盖 O(N^3) * 最小点集覆盖 **Structure 数据结构** * 求某天是星期几 * 左偏树 合并复杂度 O(LOG N) * 树状数组 * 二维树状数组 * TRIE 树(K 叉) * TRIE 树(左儿子又兄弟) * 后缀数组 O(N \* LOG N) * 后缀数组 O(N) * RMQ 离线算法 O(N\*LOGN)+O(1) * RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法(O(NLOGN + Q)) * RMQ 离线算法 O(N\*LOGN)+O(1)求解 LCA * LCA 离线算法 O(E)+O(1) * 带权值的并查集 * 快速排序 * 2 台机器工作调度 * 比较高效的大数 * 普通的大数运算 * 最长公共递增子序列 O(N^2) * 0-1 分数规划 * 最长有序子序列（递增/递减/非递增/非递减） * 最长公共子序列 * 最少找硬币问题（贪心策略-深搜实现） * 棋盘分割 * 汉诺塔 * STL 中的 PRIORITY_QUEUE * 堆栈 * 区间最大频率 * 取第 K 个元素 * 归并排序求逆序数 * 逆序数推排列数 * 二分查找 * 二分查找（大于等于 V 的第一个值） * 所有数位相加 * 吉林大学 ACM Group **Number 数论** * 递推求欧拉函数 PHI(I) * 单独求欧拉函数 PHI(X) * GCD 最大公约数 * 快速 GCD * 扩展 GCD * 模线性方程 A \* X = B (% N) * 模线性方程组 * 筛素数 [1..N] * 高效求小范围素数 [1..N] * 随机素数测试(伪素数原理) * 组合数学相关 * POLYA 计数 * 组合数 C(N, R) * 最大 1 矩阵 * 约瑟夫环问题（数学方法） * 约瑟夫环问题（数组模拟） * 取石子游戏 1 * 集合划分问题 * 大数平方根（字符串数组表示） * 大数取模的二进制方法 * 线性方程组 A[][]X[]=B[] * 追赶法解周期性方程 * 阶乘最后非零位,复杂度 O(NLOGN) **递归方法求解排列组合问题** * 类循环排列 * 全排列 * 不重复排列 * 全组合 * 不重复组合 * 应用 **模式串匹配问题总结** * 字符串 HASH * KMP 匹配算法 O(M+N) * KARP-RABIN 字符串匹配 * 基于 KARP-RABIN 的字符块匹配 * 函数名: STRSTR * BM 算法的改进的算法 SUNDAY ALGORITHM * 最短公共祖先（两个长字符串） * 最短公共祖先（多个短字符串） **Geometry 计算几何** * GRAHAM 求凸包 O(N \* LOGN) * 判断线段相交 * 求多边形重心 * 三角形几个重要的点 * 平面最近点对 O(N \* LOGN) * LIUCTIC 的计算几何库 * 求平面上两点之间的距离 * (P1-P0)\*(P2-P0)的叉积 * 确定两条线段是否相交 * 判断点 P 是否在线段 L 上 * 判断两个点是否相等 * 线段相交判断函数 * 判断点 Q 是否在多边形内 * 计算多边形的面积 * 解二次方程 AX^2+BX+C=0 * 计算直线的一般式 AX+BY+C=0 * 点到直线距离 * 直线与圆的交点，已知直线与圆相交 * 射线与圆的第一个交点 * 求点 P1 关于直线 LN 的对称点 P2 * 两直线夹角（弧度） * 射线与圆的交点 * 点是否在射线的正向 * 射线与圆的第一个交点 **ACM/ICPC 竞赛之 STL** * ACM/ICPC 竞赛之 STL 简介 * ACM/ICPC 竞赛之 STL--PAIR * ACM/ICPC 竞赛之 STL--VECTOR * ACM/ICPC 竞赛之 STL--ITERATOR 简介 * ACM/ICPC 竞赛之 STL--STRING * ACM/ICPC 竞赛之 STL--STACK/QUEUE * ACM/ICPC 竞赛之 STL--MAP * ACM/ICPC 竞赛之 STL--ALGORITHM * STL IN ACM * 头文件 * 线段树 * 求矩形并的面积（线段树+离散化+扫描线） * 求矩形并的周长（线段树+离散化+扫描线）