吉林大学ACM模板

ACM/ICPC 代码库 jojer & Fandywang 吉林大学计算机科学与技术学院 2005 级 2007-2008 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 | 最小费用流 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 2 |递推求欧拉函数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 | 大数平方根（字符串数组 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示） ...............................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 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 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 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; i1) || (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; ir.c; } }; void dijkstra(int n, const int src){ 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){ if (dist[v] > dist[u] + c) { pre[v] = u; return 1; } return 0; } int bellman (int src){ int i, j; for (i=0; i dist[u] + c ) { dist[v] = dist[u] + c; return 1; } return 0; } inline void addedge(int u, int v, int c){ pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++; } int SPFA(int src, int n) { // 此处用堆栈实现，有些时候比队列要快 int i; for( i=1; i <= n; ++i ){ // 顶点1...n vis[i] = 0; dist[i] = INF; } dist[src] = 0; int Q[E], top = 1; Q[0] = src; vis[src] = true; while( top ){ int u, v; u = Q[--top]; 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[top++] = v; vis[v] = true; } } } return dist[n]; } 5 g[i][j]=INF; // 队列实现，而且有负权回路判断—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){ int n, ml, md; while( scanf("%d%d%d", &n, &ml, &md) != EOF ){ int i, a, b, c, t; e = 0; memset(head, -1, sizeof(head)); for( i=0; i < ml; ++i ) // 边方向！！！ {// 大-小<=c, 有向边(小, 大):c scanf("%d%d%d", &a, &b, &c); if( a