吉林大学ACM算法模板大全:图论、网络流、数据结构
需积分: 35 37 浏览量
更新于2024-07-29
收藏 1.68MB PDF 举报
ACM算法模板(吉林大学)
ACM算法模板是计算机科学与技术学院的学生和ACM竞赛选手们不可或缺的参考指南。本文档涵盖了图论、网络流、数据结构等多个领域的重要算法和数据结构。
**图论**
图论是计算机科学中最重要的领域之一,涉及到图的遍历、搜索、最短路径、最小生成树等问题。本文档中,我们将讨论以下图论相关的知识点:
* 深度优先搜索(DFS):用于图的遍历,时间复杂度为O(E+V)。
* 无向图找桥:用于判断无向图中的桥边,时间复杂度为O(E+V)。
* 无向图连通度(割):用于判断无向图的连通度,时间复杂度为O(E+V)。
* 最大团问题DP+DFS:用于解决最大团问题,时间复杂度为O(2^n)。
* 欧拉路径O(E):用于判断欧拉路径,时间复杂度为O(E)。
* DIJKSTRA数组实现O(N^2):用于解决单源最短路径问题,时间复杂度为O(N^2)。
* DIJKSTRAO(E*LOGE):用于解决单源最短路径问题,时间复杂度为O(E*LOGE)。
* BELLMANFORD单源最短路O(VE):用于解决单源最短路径问题,时间复杂度为O(VE)。
* SPFA(SHORTESTPATHFASTERALGORITHM):用于解决单源最短路径问题,时间复杂度为O(E+N*LOGN)。
* 第K短路(DIJKSTRA):用于解决第K短路问题,时间复杂度为O(N*LOGN)。
* 第K短路(A*):用于解决第K短路问题,时间复杂度为O(N*LOGN)。
* PRIM求MST:用于解决最小生成树问题,时间复杂度为O(E*LOGE)。
* 次小生成树O(V^2):用于解决次小生成树问题,时间复杂度为O(V^2)。
* 最小生成森林问题(K颗树)O(MLOGM):用于解决最小生成森林问题,时间复杂度为O(MLOGM)。
* 有向图最小树形图:用于解决有向图最小树形图问题,时间复杂度为O(E+N*LOGN)。
* MINIMALSTEINERTREE:用于解决Steiner树问题,时间复杂度为O(E+N*LOGN)。
* TARJAN强连通分量:用于解决强连通分量问题,时间复杂度为O(E+N*LOGN)。
* 弦图判断:用于判断弦图,时间复杂度为O(E+N*LOGN)。
* 弦图的PERFECTELIMINATION点排列:用于解决弦图的PERFECTELIMINATION点排列问题,时间复杂度为O(E+N*LOGN)。
* 稳定婚姻问题O(N^2):用于解决稳定婚姻问题,时间复杂度为O(N^2)。
* 拓扑排序:用于解决拓扑排序问题,时间复杂度为O(E+N*LOGN)。
* 无向图连通分支(DFS/BFS邻接阵):用于解决无向图连通分支问题,时间复杂度为O(E+N*LOGN)。
* 有向图强连通分支(DFS/BFS邻接阵)O(N^2):用于解决有向图强连通分支问题,时间复杂度为O(N^2)。
* 有向图最小点基(邻接阵)O(N^2):用于解决有向图最小点基问题,时间复杂度为O(N^2)。
* FLOYD求最小环:用于解决最小环问题,时间复杂度为O(N^3)。
* 2-SAT问题:用于解决2-SAT问题,时间复杂度为O(N^2)。
**网络流**
网络流是计算机科学中的一种重要算法,涉及到最大流、最小割、最小费用流等问题。本文档中,我们将讨论以下网络流相关的知识点:
* 二分图匹配(匈牙利算法DFS实现):用于解决二分图匹配问题,时间复杂度为O(E+N*LOGN)。
* 二分图匹配(匈牙利算法BFS实现):用于解决二分图匹配问题,时间复杂度为O(E+N*LOGN)。
* 二分图匹配(HOPCROFT-CARP的算法):用于解决二分图匹配问题,时间复杂度为O(E+N*LOGN)。
* 二分图最佳匹配(KUHNMUNKRAS算法O(M*M*N)):用于解决二分图最佳匹配问题,时间复杂度为O(M*M*N)。
* 无向图最小割O(N^3):用于解决无向图最小割问题,时间复杂度为O(N^3)。
* 有上下界的最小(最大)流:用于解决有上下界的最小(最大)流问题,时间复杂度为O(E+N*LOGN)。
* DINIC最大流O(V^2*E):用于解决最大流问题,时间复杂度为O(V^2*E)。
* HLPP最大流O(V^3):用于解决最大流问题,时间复杂度为O(V^3)。
* 最小费用流O(V*E*F):用于解决最小费用流问题,时间复杂度为O(V*E*F)。
* 最小费用流O(V^2*F):用于解决最小费用流问题,时间复杂度为O(V^2*F)。
* 最佳边割集:用于解决最佳边割集问题,时间复杂度为O(E+N*LOGN)。
* 最佳点割集:用于解决最佳点割集问题,时间复杂度为O(E+N*LOGN)。
* 最小边割集:用于解决最小边割集问题,时间复杂度为O(E+N*LOGN)。
* 最小点割集(点连通度):用于解决最小点割集问题,时间复杂度为O(E+N*LOGN)。
* 最小路径覆盖O(N^3):用于解决最小路径覆盖问题,时间复杂度为O(N^3)。
* 最小点集覆盖:用于解决最小点集覆盖问题,时间复杂度为O(E+N*LOGN)。
**数据结构**
数据结构是计算机科学中的一种重要基础,涉及到数组、链表、树、图等数据结构。本文档中,我们将讨论以下数据结构相关的知识点:
* 求某天是星期几:用于解决某天是星期几问题,时间复杂度为O(1)。
* 左偏树合并复杂度O(LOGN):用于解决左偏树合并问题,时间复杂度为O(LOGN)。
* 树状数组:用于解决树状数组问题,时间复杂度为O(LOGN)。
* 二维树状数组:用于解决二维树状数组问题,时间复杂度为O(LOGN)。
* TRIE树(K叉):用于解决TRIE树问题,时间复杂度为O(LOGN)。
* TRIE树(左儿子又兄弟):用于解决TRIE树问题,时间复杂度为O(LOGN)。
* 后缀数组O(N*LOGN):用于解决后缀数组问题,时间复杂度为O(N*LOGN)。
* 后缀数组O(N):用于解决后缀数组问题,时间复杂度为O(N)。
* RMQ离线算法O(N*LOGN)+O(1):用于解决RMQ问题,时间复杂度为O(N*LOGN)+O(1)。
![](https://profile-avatar.csdnimg.cn/62953ced5d714b80af5a1e292d2794be_naruto_1860.jpg!1)
naruto_1860
- 粉丝: 1
- 资源: 5
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南:步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读:影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程:亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动:计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析:超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪:0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别:技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形:余弦曲线与正弦函数示例
- Matlab 文件操作入门:fopen、fclose、fprintf、fscanf 等函数使用详解