吉林大学ACM/ICPC代码库：算法与数据结构详解
版权申诉
9 浏览量
更新于2024-07-08
收藏 418KB PDF 举报
《代码库图书参考.pdf》是一本针对计算机科学与技术领域的教材或参考资料，主要涵盖了ACM/ICPC竞赛中常见的算法问题以及网络流、图论、数据结构等核心主题。以下是部分内容的详细解读：
1. **图论基础**：书中首先介绍了图论的基本概念，包括无向图的深度优先搜索（DFS）和广度优先搜索（BFS），以及图的连通性（如找出桥和割，计算连通度）。最大团问题使用了动态规划（DP）和深度优先搜索的组合方法。
2. **最短路径算法**：涉及迪杰斯特拉（Dijkstra）算法的两种版本，一种是标准O(N^2)时间复杂度的数组实现，另一种利用优先队列优化为O(E*LOGE)。贝尔曼-福特算法用于单源最短路径问题，时间复杂度为O(VE)。此外，还有第K短路问题（包括Dijkstra和A*搜索算法）。
3. **最小生成树问题**：介绍了Prim算法用于求最小生成树，时间复杂度为O(V^2)，以及次小生成树问题。最小生成森林问题则涉及多棵树的解决方案，时间复杂度为O(MLOGM)。
4. **有向图与树结构**：涉及有向图的最小树形图、最小Steiner树、强连通分量检测（TARJAN算法）、以及弦图的相关性质如完美消除点排列和稳定婚姻问题（O(N^2)算法）。
5. **网络流问题**：涵盖了关键的网络流算法，如最大流问题（Dinic算法为O(V^2*E)，HLPP算法为O(V^3)），最小费用流（包括两种复杂度，O(V*E*F)和O(V^2*F)），以及有上下界约束的最小（最大）流。
6. **二分图匹配**：通过匈牙利算法实现了两种不同的匹配方法（DFS和BFS），以及Hopcroft-Karp算法和Kuhn-Munkres算法。无向图的最小割问题有O(N^3)的解决方案。
7. **其他算法**：如拓扑排序、无向图的连通分支检测、有向图的强连通分支和最小点基（邻接矩阵表示下的时间复杂度均为O(N^2)）。Floyd算法用于寻找最小环，而2-SAT问题和最小路径覆盖分别涉及图论和布尔逻辑。
8. **数据结构**：内容涵盖了求特定日期的星期几，左偏树的合并操作复杂度为O(LOGN)，以及树状数组等数据结构的介绍。
这些章节内容覆盖了广泛的算法基础，对于准备ACM/ICPC比赛、学习理论计算机科学，或是从事软件开发、网络工程等领域的专业人士来说，这本书提供了宝贵的学习资源。通过深入理解和实践书中的算法，读者可以提升解决实际问题的能力。
7
for (j = 0; j < n; j++)
if (d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
for (i = 0; i < a; i++) { // vertex: 0 ~ n-1
for (j = 0; j < n; j++)
dp[1 << i][j] = d[j][ id[i] ];
}
for (i = 1; i < top; i++) {
if ( 0 == (i & (i - 1)) ) continue ;
memset(vis, 0, sizeof (vis));
for (k = 0; k < n; k++) { // init
for (dp[i][k] = inf, j = 1; j < i; j++)
if ((i | j) == i &&
dp[i][k] > dp[j][k] + dp[i - j][k])
dp[i][k] = dp[j][k] + dp[i - j][k];
}
for (j = 0; mx = inf, j < n; j++) { // update
for (k = 0; k < n; k++)
if (dp[i][k] <= mx && 0 == vis[k])
mx = dp[i][mk = k];
for (k = 0, vis[mk] = 1; k < n; k++)
if (dp[i][mk] > dp[i][k] + d[k][mk])
dp[i][mk] = dp[i][k] + d[k][mk];
}
}
}
int main( void ){
int n, a = 8;
// TODO: read data;
steiner(n, a);
// enum to find the result
for (i = 0, b = inf; z = 0, i < 256; b>z ? b=z : b, i++)
for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)
for (k = 0; k < 8; k += 2)
if ((i >> k & 3) == j)
y += 3 << k, x = id[k];
// TODO: cout << b << endl;
return 0;
}
| Tarjan 强连通分量
| INIT: vec[] 为邻接表 ; stop, cnt, scnt 置0; pre[] 置-1;
| CALL: for(i=0; i<n; ++i) if(-1==pre[i]) tarjan(i, n);
\*==================================================*/
vector< int > vec[V];
int id[V], pre[V], low[V], s[V], stop, cnt, scnt;
void tarjan( int v, int n) // vertex: 0 ~ n-1
{
int t, minc = low[v] = pre[v] = cnt++;
vector< int >::iterator pv;
s[stop++] = v;
for (pv = vec[v].begin(); pv != vec[v].end(); ++pv) {
if (-1 == pre[*pv]) tarjan(*pv, n);
if (low[*pv] < minc) minc=low[*pv];
}
if (minc < low[v]) {
low[v] = minc; return ;
}
do {
id[t = s[--stop]] = scnt; low[t] = n;
} while (t != v);
++scnt; // 强连通分量的个数
}
| 弦图判断
| INIT: g[][] 置为邻接矩阵 ;
| CALL: mcs(n); peo(n);
| 第一步 : 给节点编号 mcs(n)
| 设已编号的节点集合为 A, 未编号的节点集合为 B
| 开始时 A为空 , B 包含所有节点 .
| for num=n-1 downto 0 do {
| 在B中找节点 x, 使与 x 相邻的在 A集合中的节点数最多 ,
| 将x 编号为 num, 并从 B移入 A.
| }
| 第二步 : 检查 peo(n)
| for num=0 to n-1 do {
| 对编号为 num的点x, 设所有编号 >num且与x 相邻的点集为 C
| 在C中找出编号最小的节点 y,
| 若C中存在点 z!=y, 使得 y 与 z之间无边 , 则此图不是弦图 .
| }
| 检查完了 , 则此图是弦图 .
\*==================================================*/
int g[V][V], order[V], inv[V], tag[V];
void mcs( int n){
int i, j, k;
memset(tag, 0, sizeof (tag));
memset(order, -1, sizeof (order));
for (i = n - 1; i >= 0; i--) { // vertex: 0 ~ n-1
for (j = 0; order[j] >= 0; j++) ;
for (k = j + 1; k < n; k++)
if (order[k] < 0 && tag[k] > tag[j]) j = k;
order[j] = i, inv[i] = j;
for (k = 0; k < n; k++) if (g[j][k]) tag[k]++;
}
}
int peo( int n){
int i, j, k, w, min;
for (i = n - 2; i >= 0; i--) {
j = inv[i], w = -1, min = n;
for (k = 0; k < n; k++)
if (g[j][k] && order[k] > order[j] &&
order[k] < min)
min = order[k], w=k;
if (w < 0) continue ;
for (k = 0; k < n; k++)
if (g[j][k] && order[k] > order[w] && !g[k][w])
return 0; // no
}
return 1; // yes
}
| 弦图的 perfect elimination 点排列
| INIT: g[][] 置为邻接矩阵 ;
| CALL: cardinality(n); tag[i] 为排列中第 i 个点的标号 ;
| The graph with the property mentioned above
| is called chordal graph. A permutation s = [v1 , v2,
| ..., vn] of the vertices of such graph is called a
| perfect elimination order if each vi is a simplicial
| vertex of the subgraph of G induced by {vi ,..., vn}.
| A vertex is called simplicial if its adjacency set
| induces a complete subgraph, that is, a clique (not
| necessarily maximal). The perfect elimination order
| of a chordal graph can be computed as the following:
\*==================================================*/
procedure maximum cardinality search(G, s)
for all vertices v of G do
set label[v] to zero
end for
for all i from n downto 1 do
choose an unnumbered vertex v with largest label
set s(v) to i{number vertex v}
for all unnumbered vertices w adjacent to vertex v do
increment label[w] by one
end for
end for
end procedure
int tag[V], g[V][V], deg[V], vis[V];
void cardinality( int n)
{
int i, j, k;
memset(deg, 0, sizeof (deg));
memset(vis, 0, sizeof (vis));
for (i = n - 1; i >= 0; i--) {
for (j = 0, k = -1; j < n; j++) if (0 == vis[j]) {
if (k == -1 || deg[j] > deg[k]) k = j;
}
vis[k] = 1, tag[i] = k;
for (j = 0; j<n; j++)
if (0 == vis[j] && g[k][j]) deg[j]++;
}
}
/*==================================================*\
| 稳定婚姻问题 O(n^2)
\*==================================================*/
const int N = 1001;
struct People{
bool state;
int opp, tag;
int list[N]; // man 使用
int priority[N]; // woman 使用, 有必要的话可以和 list 合并，
以节省空间
void Init(){ state = tag = 0; }
}man[N], woman[N];
剩余44页未读，继续阅读
点击了解资源详情
210 浏览量
114 浏览量
2022-01-06 上传
2012-10-30 上传
2021-12-20 上传
2021-12-19 上传
2021-12-01 上传
2023-03-29 上传
