吉林大学ACM模板DOC版

目录

目录 .............................................. 1

Graph 图论 ........................................ 3

| DAG 的深度优先搜索标记 ............................................. 3

| 无向图找桥 ..................................................................... 3

| 无向图连通度(割) ........................................................ 3

| 第 K 短路（DIJKSTRA） ................................................. 5

| 第 K 短路（A*） ............................................................ 5

| PRIM 求 MST .................................................................... 6

| 次小生成树 O(V^2) ...................................................... 6

| 最小生成森林问题(K 颗树)O(MLOGM). ...................... 6

| 有向图最小树形图 ......................................................... 6

| MINIMAL STEINER TREE ................................................ 6

| TARJAN 强连通分量 ........................................................ 7

| 弦图判断 ......................................................................... 7

| 弦图的 PERFECT ELIMINATION 点排列 .......................... 7

| 2-SAT 问题 ..................................................................... 9

Network 网络流 ................................... 11

| 二分图匹配（匈牙利算法 DFS 实现） ...................... 11

| 二分图匹配（匈牙利算法 BFS 实现） ...................... 11

| 二分图匹配（HOPCROFT－CARP 的算法） .................. 11

| 二分图最佳匹配（KUHN MUNKRAS 算法 O(M*M*N)） 11

| 无向图最小割 O(N^3) ............................................... 12

| 有上下界的最小(最大)流 .......................................... 12

| DINIC 最大流 O(V^2 * E) ....................................... 12

| HLPP 最大流 O(V^3) ................................................ 13

| 最小路径覆盖 O(N^3) ................................................ 16

| 最小点集覆盖 ............................................................... 16

Structure 数据结构 ............................... 17

| 求某天是星期几 ........................................................... 17

| 左偏树 合并复杂度 O(LOG N) ................................... 17

| 树状数组 ....................................................................... 17

| 后缀数组 O(N * LOG N) ............................................ 18

| RMQ 离线算法 O(N*LOGN)+O(1) ............................. 19

| RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法

(O(NLOGN + Q)) ............................................................. 19

| RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA ............. 19

| LCA 离线算法 O(E)+O(1) ........................................ 20

| 带权值的并查集 ........................................................... 20

| 快速排序 ....................................................................... 20

| 2 台机器工作调度 ........................................................ 20

| 比较高效的大数 ........................................................... 20

| 普通的大数运算 ........................................................... 21

| 最长公共递增子序列 O(N^2) .................................... 22

| STL 中的 PRIORITY_QUEUE .......................................... 24

| 堆栈 ............................................................................... 24

| 区间最大频率 ............................................................... 24

| 取第 K 个元素................................................................ 25

| 归并排序求逆序数 ....................................................... 25

| 逆序数推排列数 ........................................................... 25

| 二分查找 ....................................................................... 25

| 二分查找（大于等于 V 的第一个值）........................ 25

| 所有数位相加 ............................................................... 25

Number 数论 ...................................... 26 2

| 模线性方程组 ............................................................... 26

| 筛素数 [1..N] ............................................................ 26

| 高效求小范围素数 [1..N] ........................................ 26

| 随机素数测试(伪素数原理) ...................................... 26

| 组合数学相关 ............................................................... 26

| POLYA 计数 .................................................................... 27

| 约瑟夫环问题（数组模拟） ....................................... 27

| 集合划分问题 ............................................................... 27

| 大数平方根（字符串数组表示） ............................... 28

| 大数取模的二进制方法 ............................................... 28

| 线性方程组 A[][]X[]=B[] ....................................... 28

| 追赶法解周期性方程 ................................................... 28

| 阶乘最后非零位,复杂度 O(NLOGN) ........................... 29

递归方法求解排列组合问题 ......................... 30

| 类循环排列 ................................................................... 30

| 全排列 ........................................................................... 30

| 不重复排列 ................................................................... 30

| 全组合 ........................................................................... 31

| 基于 KARP-RABIN 的字符块匹配................................. 32

| 函数名: STRSTR ........................................................... 32

| BM 算法的改进的算法 SUNDAY ALGORITHM ................ 32

| 最短公共祖先（两个长字符串） ............................... 33

| 最短公共祖先（多个短字符串） ............................... 33

Geometry 计算几何 ................................ 34

| GRAHAM 求凸包 O(N * LOGN) .................................... 34

| 判断线段相交 ............................................................... 34

| 求多边形重心 ............................................................... 34

| 三角形几个重要的点 ................................................... 34

| 判断两个点是否相等 ................................................... 35

| 线段相交判断函数 ....................................................... 35

| 判断点 Q 是否在多边形内 .......................................... 35

| 计算多边形的面积 ....................................................... 35

| 解二次方程 AX^2+BX+C=0 ........................................ 36

| 计算直线的一般式 AX+BY+C=0 ................................. 36

| 射线与圆的第一个交点 ............................................... 36

| 两直线夹角（弧度） ................................................... 36

ACM/ICPC 竞赛之 STL ............................... 37

ACM/ICPC 竞赛之 STL 简介 .......................................... 37

ACM/ICPC 竞赛之 STL--PAIR ...................................... 37

ACM/ICPC 竞赛之 STL--VECTOR .................................. 37

ACM/ICPC 竞赛之 STL--ITERATOR 简介 ...................... 38

ACM/ICPC 竞赛之 STL--STRING .................................. 38

ACM/ICPC 竞赛之 STL--STACK/QUEUE ........................ 38

ACM/ICPC 竞赛之 STL--MAP ........................................ 40

ACM/ICPC 竞赛之 STL--ALGORITHM ............................. 40

STL IN ACM ..................................................................... 41

/*==================================================*\

| DAG 的深度优先搜索标记

| INIT: edge[][]邻接矩阵; pre[], post[], tag 全置 0;

| CALL: dfstag(i, n); pre/post:开始/结束时间

\*==================================================*/

int edge[V][V], pre[V], post[V], tag;

void dfstag(int cur, int n)

{ // vertex: 0 ~ n-1

if (0 == post[i]) printf("Back Edge!\n");

else if (pre[i] > pre[cur])

printf("Down Edge!\n");

else printf("Cross Edge!\n");

}

}

post[cur] = ++tag;

}

/*==================================================*\

| CALL: dfs(0, -1, 1, n);

int bridge, edge[V][V], anc[V], pre[V], vis[V];

{ // vertex: 0 ~ n-1

if (bridge) return;

anc[cur] = pre[i];//back edge

dfs(i, cur, dep+1, n);

if (bridge) return;

if (anc[i] < anc[cur]) anc[cur] = anc[i];

if (anc[i] > pre[cur]) { bridge = 1; return; }

}

}

vis[cur] = 2;

}

/*==================================================*\

| 无向图连通度(割)

| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],deg[]置为 0;

| CALL: dfs(0, -1, 1, n);

| k=deg[0], deg[i]+1(i=1…n-1)为删除该节点后得到的连通图个数

| 注意:0 作为根比较特殊!