ACM竞赛算法集锦：图论、网络流与数据结构
需积分: 35 102 浏览量
更新于2024-07-27
收藏 1.68MB PDF 举报
"该资源是一个ACM/ICPC竞赛编程的代码库，包含了jojer和Fandywang两位作者整理的算法模板，主要涵盖图论、网络流和数据结构等方面的知识，旨在帮助参赛者快速解决各类算法问题。"
在这个代码库中，关于图论的算法模板包括：
1. DAG的深度优先搜索标记：用于处理有向无环图(DAG)的遍历和标记。
2. 无向图找桥：寻找图中的桥，即删除某条边后导致连通性改变的边。
3. 无向图连通度(割)：计算无向图的连通分量数量，以及最小割。
4. 最大团问题：使用动态规划和DFS求解图中的最大完全子图。
5. 欧拉路径：找到图中的欧拉路径，即经过每条边恰好一次的路径。
6. Dijkstra算法的两种实现：一种是简单的数组实现，时间复杂度为O(N^2)，另一种是优化后的版本，时间复杂度为O(E*LOGE)。
7. Bellman-Ford算法：求解图中的单源最短路径，时间复杂度为O(VE)。
8. SPFA算法：Shortest Path Faster Algorithm，用于求解单源最短路径。
9. 第K短路：分别用Dijkstra和A*算法求解。
10. Prim算法：求解最小生成树，时间复杂度为O(MLOGM)。
11. 次小生成树：另一种求最小生成树的方法，时间复杂度为O(V^2)。
12. 最小生成森林：处理多棵树的最小生成树问题。
13. 有向图最小树形图：求解有向图的最小树形图问题。
14. Tarjan算法：用于寻找图中的强连通分量。
15. 弦图的判断和完美消除点排列：处理弦图的特定性质。
16. 稳定婚姻问题：基于Gale-Shapley算法求解稳定婚姻分配问题。
在网络流部分，涉及的算法包括：
1. 二分图匹配：三种不同的实现方式，匈牙利算法的DFS和BFS实现，以及HOPCROFT-CARP算法。
2. Kuhn-Munkres算法：求解二分图的最佳匹配，时间复杂度为O(M*M*N)。
3. 无向图最小割：计算图的最小割，用于分离网络。
4. 有上下界限制的最小(最大)流问题。
5. Dinic算法：求解最大流问题，时间复杂度为O(V^2*E)。
6. HLPP算法：Highway-Linkage-Path-Push-Relabel的最大流算法，时间复杂度为O(V^3)。
7. 最小费用流：同时考虑流量和费用的网络流问题，有两种不同复杂度的实现。
8. 最佳边割集、最佳点割集和最小边/点割集：与网络流相关的割集优化问题。
9. 最小路径覆盖：寻找图中最小的路径集合，覆盖所有顶点。
10. 最小点集覆盖：寻找最小的点集合，使得每个边至少有一个端点在集合中。
最后，数据结构方面：
1. 求某天是星期几：根据日期计算星期。
2. 左偏树：一种特殊的二叉堆，具有合并操作的低复杂度。
3. 树状数组：用于快速查询和更新区间加法的数组结构。
4. 二维树状数组：扩展树状数组到二维情况，处理二维区间加法。
5. TRIE树：前缀树，用于高效存储和查找字符串。
6. 后缀数组：处理字符串的后缀，有O(N*LOGN)和O(N)两种构建方法。
7. RQ(Range Minimum Query)：区间最小值查询，离线算法实现为O(N*LOGN)+O(1)。
这些算法模板对于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页未读，继续阅读
点击了解资源详情
点击了解资源详情
点击了解资源详情
2012-03-04 上传
2013-05-20 上传
2024-05-02 上传
2011-07-28 上传
2011-05-08 上传
2020-12-16 上传
chjandroid
- 粉丝: 1
- 资源: 4
我的内容管理
展开
最新资源
- C语言数组操作：高度检查器编程实践
- 基于Swift开发的嘉定单车LBS iOS应用项目解析
- 钗头凤声乐表演的二度创作分析报告
- 分布式数据库特训营全套教程资料
- JavaScript开发者Robert Bindar的博客平台
- MATLAB投影寻踪代码教程及文件解压缩指南
- HTML5拖放实现的RPSLS游戏教程
- HT://Dig引擎接口，Ampoliros开源模块应用
- 全面探测服务器性能与PHP环境的iprober PHP探针v0.024
- 新版提醒应用v2：基于MongoDB的数据存储
- 《我的世界》东方大陆1.12.2材质包深度体验
- Hypercore Promisifier: JavaScript中的回调转换为Promise包装器
- 探索开源项目Artifice：Slyme脚本与技巧游戏
- Matlab机器人学习代码解析与笔记分享
- 查尔默斯大学计算物理作业HP2解析
- GitHub问题管理新工具：GIRA-crx插件介绍
