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
| 大数平方根（字符串数组表示） ...............................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<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;
path[beg] = -1; // 树根的标记
int pre = beg;
for (i=1; i<n; i++){
min = INF;
4
dist[v] = dist[u] + c;
for (j=0; j<n; j++)
// 下面的加法可能导致溢出,INF不能取太大
if (vis[j]==0 &&
lowcost[pre]+cost[pre][j]<lowcost[j]){
lowcost[j] = lowcost[pre] + cost[pre][j];
path[j] = pre;
}
for (j=0; j<n; j++)
if (vis[j] == 0 && lowcost[j] < min){
min = lowcost[j]; pre = j;
}
vis[pre] = 1;
}
}
/*==================================================*\
| Dijkstra O(E * log E)
| INIT: 调用init(nv, ne)读入边并初始化;
| CALL: dijkstra(n, src); dist[i]为src到i的最短距离
\*==================================================*/
#define typec int // type of cost
const typec inf = 0x3f3f3f3f; // max of cost
typec cost[E], dist[V];
int e, pnt[E], nxt[E], head[V], prev[V], vis[V];
struct qnode {
int v; typec c;
qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {}
bool operator < (const qnode& r) const { return c>r.c; }
};
void dijkstra(int n, const int src){
qnode mv;
int i, j, k, pre;
priority_queue<qnode> que;
vis[src] = 1; dist[src] = 0;
que.push(qnode(src, 0));
for (pre = src, i=1; i<n; i++) {
for (j = head[pre]; j != -1; j = nxt[j]) {
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;
}
}
while (!que.empty() && vis[que.top().v] == 1)
que.pop();
if (que.empty()) break;
mv = que.top(); que.pop();
vis[pre = mv.v] = 1;
}
}
inline void addedge(int u, int v, typec c){
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
}
void init(int nv, int ne){
int i, u, v; typec c;
e = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(prev, -1, sizeof(prev));
for (i = 0; i < nv; i++) dist[i] = inf;
for (i = 0; i < ne; ++i) {
scanf("%d%d%d", &u, &v, &c);// %d: type of cost
addedge(u, v, c); // vertex: 0 ~ n-1, 单向边
}
}
/*==================================================*\
| BellmanFord 单源最短路 O(VE)
| 能在一般情况下，包括存在负权边的情况下，解决单源最短路径问题
| INIT: edge[E][3]为边表
| CALL: bellman(src);有负环返回0;dist[i]为src到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<n; ++i) {
dist[i] = inf; pre[i] = -1;
}
dist[src] = 0; bool flag;
for (i=1; i<n; ++i){
flag = false; // 优化
for (j=0; j<m; ++j) {
if( 1 == relax(edge[j][0], edge[j][1],
edge[j][2]) ) flag = true;
}
if( !flag ) break; }
for (j=0; j<m; ++j) {
if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
return 0; // 有负圈
}
return 1;
}
/*==================================================*\
| SPFA(Shortest Path Faster Algorithm)
Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 它可以在
O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
原理：只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻
接点的距离估计值的改变。
判断负权回路：记录每个结点进队次数，超过|V|次表示有负权。
\*==================================================*/
// POJ 3159 Candies
const int INF = 0x3F3F3F3F;
const int V = 30001;
const int E = 150001;
int pnt[E], cost[E], nxt[E];
int e, head[V]; int dist[V]; bool vis[V];
int main(void){
int n, m;
while( scanf("%d%d", &n, &m) != EOF ){
int i, a, b, c;
e = 0;
memset(head, -1, sizeof(head));
for( i=0; i < m; ++i )
{// b-a <= c, 有向边(a, b):c ，边的方向！！！
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
printf("%d\n", SPFA(1, n));
}
return 0;
}
int relax(int u, int v, int c){
if( dist[v] > 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];
}
