作业帮noip图论需要弄懂什么?
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 13:25:39
noip图论需要弄懂什么?
noip图论需要弄懂什么?
noip图论需要弄懂什么?
【图论】图的表示：邻接矩阵,邻接表,边表
传递闭包和floyd
最小生成树算法(至少会一种)
单源最短路dijkstra（O(n2)）或者bellman（spfa优化,O(km)）
拓扑排序
【树】 树的先序、中序、后序遍历
树中的最长路（两遍bfs或者dfs）
并查集
有能力的话：
Dijkstra算法的堆优化、求割点、求割边、强连通分量、欧拉路（边一次）、汉密尔顿回路（点一次）、差分约束系统
匹配算法（最大匹配,最小点覆盖,最小路径覆盖,最大独立集)
网络流算法（最大流dinic,最小费用流spfa）
【动态规划】动态规划的优化（快速幂,改变状态,优化转移,单调性,四边形不等式）
归并树(逆序对)平衡树（sbt、treap、splay）后缀数组
树的最长链，最短路问题（dijkstra，SPFA，floyd），最小生成树问题（prim，kruskal），二分图检验，强连通分量（tarjan）等等。NOIP没有考纲，他们喜欢出个网络流你也不能怪他，所以知道的越多越好。
说到底掌握所有算法是远远不够的，反而掌握不全也可能拿高分。不可能有哪道题考裸算法，还有细节比如treeDP的处理，还有灵感比如建图方法。大量做题吧，做题是提高OI的唯...
全部展开
树的最长链，最短路问题（dijkstra，SPFA，floyd），最小生成树问题（prim，kruskal），二分图检验，强连通分量（tarjan）等等。NOIP没有考纲，他们喜欢出个网络流你也不能怪他，所以知道的越多越好。
说到底掌握所有算法是远远不够的，反而掌握不全也可能拿高分。不可能有哪道题考裸算法，还有细节比如treeDP的处理，还有灵感比如建图方法。大量做题吧，做题是提高OI的唯一方法。
收起