第1页 / 共46页
第2页 / 共46页
第3页 / 共46页
第4页 / 共46页
第5页 / 共46页
第6页 / 共46页
第7页 / 共46页
第8页 / 共46页
ACM/ICPC算法大全(c语言).pdf
ACM/ICPC 代码库
吉林大学计算机科学与技术学院 2005 级
2007-2008
文档变更记录
修订日期
修订内容
修订版本
修订人
2007
2008.10
创建
修订
1.0
1.1
jojer（sharang、xwbsw、Liuctic）
Fandywang
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 ................................................ 6
| TARJAN 强连通分量 ........................................................ 7
| 弦图判断 ......................................................................... 7
| 弦图的 PERFECT ELIMINATION 点排列 .......................... 7
| 稳定婚姻问题 O(N^2) .................................................. 7
| 拓扑排序 ......................................................................... 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) ....................................... 13
1
| 最小费用流 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 叉) .............................................................. 17
| 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
| 汉诺塔 ........................................................................... 23
| STL 中的 PRIORITY_QUEUE .......................................... 24
| 堆栈 ............................................................................... 24
| 区间最大频率 ............................................................... 24
| 取第 K 个元素................................................................ 25
| 归并排序求逆序数 ....................................................... 25
| 逆序数推排列数 ........................................................... 25
| 二分查找 ....................................................................... 25
| 二分查找（大于等于 V 的第一个值）........................ 25
| 所有数位相加 ............................................................... 25
Number 数论 ...................................... 26
|递推求欧拉函数 PHI(I) ............................................... 26
|单独求欧拉函数 PHI(X) ............................................... 26
| GCD 最大公约数 .......................................................... 26
| 快速 GCD ...................................................................... 26
| 扩展 GCD ...................................................................... 26
| 模线性方程 A * X = B (% N) .................................. 26
| 模线性方程组 ............................................................... 26
| 筛素数 [1..N] ............................................................ 26
| 高效求小范围素数 [1..N] ........................................ 26
| 随机素数测试(伪素数原理) ...................................... 26
| 组合数学相关 ............................................................... 26
| POLYA 计数 .................................................................... 27
| 组合数 C(N, R) ........................................................... 27
| 最大 1 矩阵 ................................................................... 27
| 约瑟夫环问题（数学方法） ....................................... 27
| 约瑟夫环问题（数组模拟） ....................................... 27
| 取石子游戏 1 ................................................................ 27
| 集合划分问题 ............................................................... 27
| 大数平方根（字符串数组表示） ............................... 28
| 大数取模的二进制方法 ............................................... 28
| 线性方程组 A[][]X[]=B[] ....................................... 28
| 追赶法解周期性方程 ................................................... 28
| 阶乘最后非零位,复杂度 O(NLOGN) ........................... 29
递归方法求解排列组合问题 ......................... 30
| 类循环排列 ................................................................... 30
| 全排列 ........................................................................... 30
| 不重复排列 ................................................................... 30
| 全组合 ........................................................................... 31
| 不重复组合 ................................................................... 31
| 应用 ............................................................................... 31
模式串匹配问题总结 ............................... 32
| 字符串 HASH .................................................................. 32
| KMP 匹配算法 O(M+N) ............................................... 32
| KARP-RABIN 字符串匹配 ............................................. 32
| 基于 KARP-RABIN 的字符块匹配................................. 32
| 函数名: STRSTR ........................................................... 32
| BM 算法的改进的算法 SUNDAY ALGORITHM ................ 32
| 最短公共祖先（两个长字符串） ............................... 33
| 最短公共祖先（多个短字符串） ............................... 33
Geometry 计算几何 ................................ 34
| GRAHAM 求凸包 O(N * LOGN) .................................... 34
| 判断线段相交 ............................................................... 34
| 求多边形重心 ............................................................... 34
| 三角形几个重要的点 ................................................... 34
| 平面最近点对 O(N * LOGN) ...................................... 34
| LIUCTIC 的计算几何库 ................................................ 35
| 求平面上两点之间的距离 ........................................... 35
| (P1-P0)*(P2-P0)的叉积 ....................................... 35
| 确定两条线段是否相交 ............................................... 35
| 判断点 P 是否在线段 L 上 ............................................ 35
| 判断两个点是否相等 ................................................... 35
| 线段相交判断函数 ....................................................... 35
| 判断点 Q 是否在多边形内 .......................................... 35
| 计算多边形的面积 ....................................................... 35
| 解二次方程 AX^2+BX+C=0 ........................................ 36
| 计算直线的一般式 AX+BY+C=0 ................................. 36
| 点到直线距离 ............................................................... 36
| 直线与圆的交点，已知直线与圆相交 ....................... 36
| 点是否在射线的正向 ................................................... 36
| 射线与圆的第一个交点 ............................................... 36
| 求点 P1 关于直线 LN 的对称点 P2 .............................. 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
头文件 ............................................................................... 42
线段树 ........................................... 43
求矩形并的面积（线段树+离散化+扫描线） ............... 43
求矩形并的周长（线段树+离散化+扫描线） ............... 44
2
Graph 图论
if (pre[i] < anc[cur])
if (pre[i] < anc[cur])
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");
}
// vertex: 0 ~ n-1
if (bridge) return;
vis[cur] = 1; pre[cur] = anc[cur] = dep;
for (int i=0; i1) ||
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; }
(cnt!=0 && anc[i]>=pre[cur]))
++deg[cur]; // link degree of a vertex
p = stk[dep][j];
if (g[k][p]) stk[dep + 1][cnt++] = p;
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++) {
}
dfs(n, cnt, dep + 1);
/*==================================================*\
| 最大团问题 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++) {
}
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){
stk[ top++ ] = v;
w = adj[v][ --cnt[v] ];
adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ];
// 处理的是无向图—-边是双向的，删除v->w后，还要处理删除w->v
}
void elpath (int b, int n){ // begin from b
}
/*==================================================*\
| 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){
min = INF;
int i, j;
for (i = 0; i < n; ++i) // vertex: 0 ~ n-1
printf("%d", b);
for (top = 0; path(b) == b && top != 0; ) {
}
printf("\n");
int i, j, min;
memset(vis, 0, sizeof(vis));
vis[beg] = 1;
for (i=0; i 0; v = w) {
}
return v;
for (j = 0; j < cnt[i]; ++j)
idx[i][ adj[i][j] ] = j;
lowcost[i] = cost[beg][i]; path[i] = beg;
b = stk[ --top ];
printf("-%d", b);
3
}
min = lowcost[j]; pre = j;
lowcost[j] = lowcost[pre] + cost[pre][j];
path[j] = pre;
k = pnt[j];
if (vis[k] == 0 &&
}
dist[pre] + cost[j] < dist[k]){
dist[k] = dist[pre] + cost[j];
que.push(qnode(pnt[j], dist[k]));
prev[k] = pre;
for (j=0; jr.c; }
if (vis[j]==0 &&
}
if (vis[j] == 0 && lowcost[j] < min){
}
qnode mv;
int i, j, k, pre;
priority_queue que;
vis[src] = 1; dist[src] = 0;
que.push(qnode(src, 0));
for (pre = src, i=1; i=表示求最
小值, 作为最长路，<=表示求最大值, 作为最短路 （v-u <= c:a[u][v] =
c）
\*==================================================*/
#define typec int // type of cost
const typec inf=0x3f3f3f3f; // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c){
for (j = head[pre]; j != -1; j = nxt[j]) {
}
while (!que.empty() && vis[que.top().v] == 1)
if (que.empty()) break;
mv = que.top(); que.pop();
vis[pre = mv.v] = 1;
scanf("%d%d%d", &u, &v, &c);// %d: type of cost
addedge(u, v, c); // vertex: 0 ~ n-1, 单向边
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
if (dist[v] > dist[u] + c) {
dist[v] = dist[u] + c;
que.pop();
4
pre[v] = u; return 1;
}
return 0;
}
int bellman (int src){
int i, j;
for (i=0; i dist[u] + c ) {
}
return 0;
v = pnt[i];
if( 1 == relax(u, v, cost[i]) && !vis[v] ) {
}
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
dist[v] = dist[u] + c; return 1;
Q[top++] = v; vis[v] = true;
vis[i] = 0; dist[i] = INF;
scanf("%d%d%d", &a, &b, &c);
if( a < b ) swap(t, a, b);
dist[v] = dist[u] + c; return 1;
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
scanf("%d%d%d", &a, &b, &c);
if( a > b) swap(t, a, b);
addedge(a, b, c);
if( dist[v] > dist[u] + c ) {
}
return 0;
int n, ml, md;
while( scanf("%d%d%d", &n, &ml, &md) != EOF ){
//for( i=1; i <= n; ++i ) printf("%d\n", dist[i]);
}
return 0;
int i, a, b, c, t;
e = 0;
memset(head, -1, sizeof(head));
for( i=0; i < ml; ++i ) // 边方向！！！
{// 大-小<=c, 有向边(小, 大):c
}
for( i=0; i < md; ++i )
{// 大-小>=c ==> 小-大<=-c, 有向边(大, 小):-c
}
printf("%d\n", SPFA(1, n));
// 队列实现，而且有负权回路判断—POJ 3169 Layout
#define swap(t, a, b) (t=a, a=b, b=t)
const int INF = 0x3F3F3F3F;
const int V = 1001;
const int E = 20001;
int pnt[E], cost[E], nxt[E];
int e, head[V], dist[V];
bool vis[V];
int cnt[V]; // 入队列次数
int main(void){
addedge(a, b, -c);
}
int relax(int u, int v, int c){
}
inline void addedge(int u, int v, int c){
}
int SPFA(int src, int n){// 此处用队列实现
为入队列次数，用来判断是否存在负权回路
目可省！！！
}
/*==================================================*\
| 第 K 短路（Dijkstra）
| dij变形，可以证明每个点经过的次数为小于等于K，所有把dij的数组dist
| 由一维变成2维，记录经过该点1次，2次。。。k次的最小值。
| 输出dist[n-1][k]即可
\*==================================================*/
//WHU1603
int g[1010][1010];
int n,m,x;
const int INF=1000000000;
int v[1010];
int dist[1010][20];
int main(){
while (scanf("%d%d%d",&n,&m,&x)!=EOF){
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=INF;
int i;
memset(cnt, 0, sizeof(cnt)); // 入队次数
memset(vis, false, sizeof(vis));
for( i=1; i <= n; ++i ) dist[i] = INF;
dist[src] = 0;
queue Q;
Q.push(src); vis[src] = true; ++cnt[src];
while( !Q.empty() ){
}
if( dist[n] == INF ) return -2; // src与n不可达，有些题
return dist[n]; // 返回src到n的最短距离，根据题意不同而改变
int u, v;
u = Q.front(); Q.pop(); vis[u] = false;
for( i=head[u]; i != -1; i=nxt[i] ){
}
v = pnt[i];
if( 1 == relax(u, v, cost[i]) && !vis[v] ) {
Q.push(v); vis[v] = true;
if( (++cnt[v]) > n ) return -1; // cnt[i]
}
for (int i=0;i0;j--)
if (dist[i][j]b.fi;
return a.gi>b.gi;
}
int id=s[0].id,fi=s[0].fi,gi=s[0].gi;
if (id==n-1) cnt++;
if (cnt==x) return fi;
pop_heap(s,s+ct);
if (v[j] && dist[j]
gr[i][j]=g[i][j]=INF;
if (cp[i] == i) return i;
return cp[i] = iroot(cp[i]);
i = iroot(eg[j].u); k = iroot(eg[j].v);
if (k != i && dis[k] > eg[j].c) {
}
dis[k] = eg[j].c;
to[k] = i;
for (int j=0;j T1 -->
T2 --> ... --> Tn (T) 变成最小生成树.所谓的变换是，每次把T_i中的
}
/*==================================================*\
某条边换成T中的一条边, 而且树T_(i+1)的权小于等于T_i的权.
| Minimal Steiner Tree
具体操作是：
| G(V, E), A是V的一个子集, 求至少包含A中所有点的最小子树.
step 1. 在T_i中任取一条不在T中的边u_v.
| 时间复杂度: O(N^3 + N * 2^A * (2^A + N))
step 2. 把边u_v去掉，就剩下两个连通分量A和B，在T中，必有唯一的
| INIT: d[][]距离矩阵; id[]置为集合A中点的标号;
边u'_v' 连结A和B.
| CALL: steiner(int n, int a);
step 3. 显然u'_v'的权比u_v小 (否则,u_v就应该在T中).把u'_v'
| main()函数解决的题目: Ticket to Ride, NWERC 2006/2007
替换u_v即得树T_(i+1).
| 给4个点对(a1, b1) ... (a4, b4),
特别地：取Tn为任一棵次小生成树，T_(n-1) 也就是次小生成树且跟T
| 求min(sigma(dist[ai][bi])),其中重复的路段只能算一次.
差一条边. 结论得证.
| 这题要找出一个steiner森林, 最后要对森林中树的个数进行枚举
算法：只要充分利用以上结论, 即得V^2的算法. 具体如下：
\*==================================================*/
step 1. 先用prim求出最小生成树T. 在prim的同时，用一个矩阵
#define typec int // type of cost
max[u][v] 记录在T中连结任意两点u,v的唯一的路中权值最大的那条边的
const typec inf = 0x3f3f3f3f; // max of cost
权值. (注意这里). 这是很容易做到的，因为prim是每次增加一个结点s, 而
int vis[V], id[A]; //id[]: A中点的标号
typec d[V][V], dp[1< lowc[j]) {
}
minc = lowc[j]; p = j;
int i, j, k, mx, mk, top = (1 << a);
for (k = 0; k < n; k++) for (i = 0; i < n; i++)
i = iroot(eg[j].u); k = iroot(eg[j].v);
if (k != i && tag[k] == -2) eg[j].c -= dis[k];
tag[j] = i;
}
return res;
if (0 == vis[j] && lowc[j] > cost[p][j])
lowc[j] = cost[p][j];
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
