吉林大学
ACM/ICPC 代码库
吉林大学计算机科学与技术学院 2005 级
2007-2008
吉林大学 ACM Group
1
文档变更记录
修订日期 修订内容 修订版本 修订人
2007
创建
1.0
jojer（sharang、xwbsw、Liuctic）
2008.10
修订
1.1
Fandywang
吉林大学 ACM Group
1
目录
目录 .............................................. 1
Graph 图论 ........................................ 3
| DAG 的深度优先搜索标记 ............................................. 3
| 无向图找桥 ..................................................................... 3
| 无向图连通度(割) ........................................................ 3
| 最大团问题 DP + DFS ................................................. 3
| 欧拉路径 O(E) ............................................................... 3
| DIJKSTRA 数组实现 O（N^2） ..................................... 3
| DIJKSTRA O(E * LOG E) ............................................. 4
| BELLMANFORD 单源最短路 O(VE) ................................. 4
| SPFA(SHORTEST PATH FASTER ALGORITHM) .............. 4
| 第 K 短路（DIJKSTRA） ................................................. 5
| 第 K 短路（A*） ............................................................ 5
| PRIM 求 MST .................................................................... 6
| 次小生成树 O(V^2) ...................................................... 6
| 最小生成森林问题(K 颗树)O(MLOGM). ...................... 6
| 有向图最小树形图 ......................................................... 6
| MINIMAL STEINER TREE ................................................ 7
| TARJAN 强连通分量 ........................................................ 7
| 弦图判断 ......................................................................... 7
| 弦图的 PERFECT ELIMINATION 点排列 .......................... 7
| 稳定婚姻问题 O(N^2) .................................................. 8
| 拓扑排序 ......................................................................... 8
| 无向图连通分支(DFS/BFS 邻接阵) ............................. 8
| 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) ............ 8
| 有向图最小点基(邻接阵)O(N^2)............................... 9
| FLOYD 求最小环 .............................................................. 9
| 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(V * E * F) ....................................... 14
| 最小费用流 O(V^2 * F) ........................................... 14
| 最佳边割集 ................................................................... 15
| 最佳点割集 ................................................................... 15
| 最小边割集 ................................................................... 15
| 最小点割集（点连通度） ........................................... 16
| 最小路径覆盖 O(N^3) ................................................ 16
| 最小点集覆盖 ............................................................... 16
Structure 数据结构 ............................... 17
| 求某天是星期几 ........................................................... 17
| 左偏树 合并复杂度 O(LOG N) ................................... 17
| 树状数组 ....................................................................... 17
| 二维树状数组 ............................................................... 17
| TRIE 树(K 叉) .............................................................. 18
| TRIE 树(左儿子又兄弟) ............................................. 18
| 后缀数组 O(N * LOG N) ............................................ 18
| 后缀数组 O(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
| 0-1 分数规划 ............................................................... 22
| 最长有序子序列（递增/递减/非递增/非递减） .... 22
| 最长公共子序列 ........................................................... 23
| 最少找硬币问题（贪心策略-深搜实现） ................. 23
| 棋盘分割 ....................................................................... 23
| 汉诺塔 ........................................................................... 24
| STL 中的 PRIORITY_QUEUE .......................................... 24
| 堆栈 ............................................................................... 24
| 区间最大频率 ............................................................... 24
| 取第 K 个元素................................................................ 25
| 归并排序求逆序数 ....................................................... 25
| 逆序数推排列数 ........................................................... 25
| 二分查找 ....................................................................... 25
| 二分查找（大于等于 V 的第一个值）........................ 26
| 所有数位相加 ............................................................... 26
吉林大学 ACM Group
2
Number 数论 ...................................... 27
|递推求欧拉函数 PHI(I) ............................................... 27
|单独求欧拉函数 PHI(X) ............................................... 27
| GCD 最大公约数 .......................................................... 27
| 快速 GCD ...................................................................... 27
| 扩展 GCD ...................................................................... 27
| 模线性方程 A * X = B (% N) .................................. 27
| 模线性方程组 ............................................................... 27
| 筛素数 [1..N] ............................................................ 27
| 高效求小范围素数 [1..N] ........................................ 27
| 随机素数测试(伪素数原理) ...................................... 27
| 组合数学相关 ............................................................... 27
| POLYA 计数 .................................................................... 28
| 组合数 C(N, R) ........................................................... 28
| 最大 1 矩阵 ................................................................... 28
| 约瑟夫环问题（数学方法） ....................................... 28
| 约瑟夫环问题（数组模拟） ....................................... 28
| 取石子游戏 1 ................................................................ 28
| 集合划分问题 ............................................................... 28
| 大数平方根（字符串数组表示） ............................... 29
| 大数取模的二进制方法 ............................................... 29
| 线性方程组 A[][]X[]=B[] ....................................... 29
| 追赶法解周期性方程 ................................................... 30
| 阶乘最后非零位,复杂度 O(NLOGN) ........................... 30
递归方法求解排列组合问题 ......................... 31
| 类循环排列 ................................................................... 31
| 全排列 ........................................................................... 31
| 不重复排列 ................................................................... 31
| 全组合 ........................................................................... 32
| 不重复组合 ................................................................... 32
| 应用 ............................................................................... 33
模式串匹配问题总结 ............................... 33
| 字符串 HASH .................................................................. 33
| KMP 匹配算法 O(M+N) ............................................... 33
| KARP-RABIN 字符串匹配 ............................................. 33
| 基于 KARP-RABIN 的字符块匹配................................. 33
| 函数名: STRSTR ........................................................... 34
| BM 算法的改进的算法 SUNDAY ALGORITHM ................ 34
| 最短公共祖先（两个长字符串） ............................... 34
| 最短公共祖先（多个短字符串） ............................... 34
Geometry 计算几何 ................................ 35
| GRAHAM 求凸包 O(N * LOGN) .................................... 35
| 判断线段相交 ............................................................... 35
| 求多边形重心 ............................................................... 35
| 三角形几个重要的点 ................................................... 35
| 平面最近点对 O(N * LOGN) ...................................... 35
| LIUCTIC 的计算几何库 ................................................ 36
| 求平面上两点之间的距离 ........................................... 36
| (P1-P0)*(P2-P0)的叉积 ....................................... 36
| 确定两条线段是否相交 ............................................... 36
| 判断点 P 是否在线段 L 上 ............................................ 36
| 判断两个点是否相等 ................................................... 36
| 线段相交判断函数 ....................................................... 36
| 判断点 Q 是否在多边形内 .......................................... 37
| 计算多边形的面积 ....................................................... 37
| 解二次方程 AX^2+BX+C=0 ........................................ 37
| 计算直线的一般式 AX+BY+C=0 ................................. 37
| 点到直线距离 ............................................................... 37
| 直线与圆的交点，已知直线与圆相交 ....................... 37
| 点是否在射线的正向 ................................................... 37
| 射线与圆的第一个交点 ............................................... 37
| 求点 P1 关于直线 LN 的对称点 P2 .............................. 37
| 两直线夹角（弧度） ................................................... 37
ACM/ICPC 竞赛之 STL ............................... 38
ACM/ICPC 竞赛之 STL 简介 .......................................... 38
ACM/ICPC 竞赛之 STL--PAIR ...................................... 38
ACM/ICPC 竞赛之 STL--VECTOR .................................. 39
ACM/ICPC 竞赛之 STL--ITERATOR 简介 ...................... 39
ACM/ICPC 竞赛之 STL--STRING .................................. 40
ACM/ICPC 竞赛之 STL--STACK/QUEUE ........................ 40
ACM/ICPC 竞赛之 STL--MAP ........................................ 41
ACM/ICPC 竞赛之 STL--ALGORITHM ............................. 42
STL IN ACM ..................................................................... 43
头文件 ............................................................................... 44
线段树 ........................................... 44
求矩形并的面积（线段树+离散化+扫描线） ............... 44
求矩形并的周长（线段树+离散化+扫描线） ............... 45
吉林大学 ACM Group
3
Graph 图论
/*==================================================*\
| 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
pre[cur] = ++tag;
for (int i=0; i<n; ++i) if (edge[cur][i]) {
if (0 == pre[i]) {
printf("Tree Edge!\n");
dfstag(i, n);
} else {
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;
}
/*==================================================*\
| 无向图找桥
| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],bridge 置0;
| CALL: dfs(0, -1, 1, n);
\*==================================================*/
int bridge, edge[V][V], anc[V], pre[V], vis[V];
void dfs(int cur, int father, int dep, int n)
{ // vertex: 0 ~ n-1
if (bridge) return;
vis[cur] = 1; pre[cur] = anc[cur] = dep;
for (
int i=0; i<n; ++i) if (edge[cur][i]) {
if (i != father && 1 == vis[i]) {
if (pre[i] < anc[cur])
anc[cur] = pre[i];//back edge
}
if (0 == vis[i]) { //tree 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作为根比较特殊!
\*==================================================*/
int edge[V][V], anc[V], pre[V], vis[V], deg[V];
void dfs(int cur, int father, int dep, int n)
{// vertex: 0 ~ n-1
int cnt = 0;
vis[cur] = 1; pre[cur] = anc[cur] = dep;
for (int i=0; i<n; ++i) if (edge[cur][i]) {
if (i != father && 1 == vis[i]) {
if (pre[i] < anc[cur])
anc[cur] = pre[i];//back edge
}
if (0 == vis[i]) { //tree edge
dfs(i, cur, dep+1, n);
++cnt; // 分支个数
if (anc[i] < anc[cur]) anc[cur] = anc[i];
if ((cur==0 && cnt>1) ||
(cnt!=0 && anc[i]>=pre[cur]))
++deg[cur]; // link degree of a vertex
}
}
vis[cur] = 2;
}
/*==================================================*\
| 最大团问题 DP + DFS
| INIT: g[][]邻接矩阵;
| CALL: res = clique(n);
\*==================================================*/
int g[V][V], dp[V], stk[V][V], mx;
int dfs(int n, int ns, int dep){
if (0 == ns) {
if (dep > mx) mx = dep;
return 1;
}
int i, j, k, p, cnt;
for (i = 0; i < ns; i++) {
k = stk[dep][i]; cnt = 0;
if (dep + n - k <= mx) return 0;
if (dep + dp[k] <= mx) return 0;
for (j = i + 1; j < ns; j++) {
p = stk[dep][j];
if (g[k][p]) stk[dep + 1][cnt++] = p;
}
dfs(n, cnt, dep + 1);
}
return 1;
}
int clique(int n){
int i, j, ns;
for (mx = 0, i = n - 1; i >= 0; i--) {
// vertex: 0 ~ n-1
for (ns = 0, j = i + 1; j < n; j++)
if (g[i][j]) stk[1][ ns++ ] = j;
dfs(n, ns, 1); dp[i] = mx;
}
return mx;
}
/*==================================================*\
| 欧拉路径 O(E)
| INIT: adj[][]置为图的邻接表; cnt[a]为a点的邻接点个数;
| CALL: elpath(0); 注意
:不要有自向边
\*==================================================*/
int adj[V][V], idx[V][V], cnt[V], stk[V], top;
int path(int v){
for (int w ; cnt[v] > 0; v = w) {
stk[ top++ ] = v;
w = adj[v][ --cnt[v] ];
adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ];
// 处理的是无向图—-边是双向的，删除v->w后，还要处理删除w->v
}
return v;
}
void elpath (int b, int n){ // begin from b
int i, j;
for (i = 0; i < n; ++i) // vertex: 0 ~ n-1
for (j = 0; j < cnt[i]; ++j)
idx[i][ adj[i][j] ] = j;
printf("%d", b);
for (top = 0; path(b) == b && top != 0; ) {
b = stk[ --top ];
printf("-%d", b);
}
printf("\n");
}
/*==================================================*\
| Dijkstra 数组实现 O（N^2）
| Dijkstra --- 数组实现(在此基础上可直接改为STL的Queue实现)
| lowcost[] --- beg到其他点的最近距离
| path[] -- beg为根展开的树，记录父亲结点
\*==================================================*/
#define INF 0x03F3F3F3F
const int N;
int path[N], vis[N];
void Dijkstra(int cost[][N], int lowcost[N], int n, int beg){
int i, j, min;
memset(vis, 0, sizeof(vis));
vis[beg] = 1;
for (i=0; i<n; i++){
lowcost[i] = cost[beg][i]; path[i] = beg;
}
lowcost[beg] = 0;
评论0
最新资源