#include <iostream> #include <set> using namespace std; int main() { int n; cin >> n; set<int> s; s.insert(0); for (int i = 0; i < n; i ++) { int a;…

什么是树形 DP？树形 DP（Dynamic Programming on Trees）是一种在 树结构 上使用 动态规划 解决问题的方法。它的核心思想是 自底向上 递归计算，每个节点的状态依赖于它的子节点的计算结果。如果你熟悉普通的 动态规划（DP），你可以把树形 DP 理解为：普通 DP 在一维或二维数组上进行（如最长子序列、背包问题）。树形 …

树与图的存储树是一种特殊的图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b, b->a。因此我们可以只考虑有向图的存储。n：点数，m：边数稀疏图:如果m和n是一个级别的，用邻接表。稠密图:如果m和n^2是一个级别的，用邻接矩阵。(1) 邻接矩阵：g[a][b] 存储边 a->b，先初始化g位正无穷memset(…

二分图 当且仅当图中不含奇数环。二分图就是将图中的点分成左右两个集合，每条边都在两个集合之间染色法判断是不是二分图思路：利用dfs将每个点进行染色，将某个点染成白色，则以这个点为中心的其他点染成黑色，用1表示白色，用2表示黑色，0表示没有染过色，可以建立一个数组color[]，来存储染色情况，每次dfs先判断是否染色，如果没有就染成和上一个点不一样…

朴素prim（普利姆）算法一般用这个算法解决稠密图，用邻接矩阵来存图。是无向边所以就是存两条反向的单向边，来表示。思路和dijkstra算法差不多。开一个n次遍历，每次遍历都从还没加到集合中的点选一个到集合距离最小的点，dijkstra算法求的是最短路，所以是到原点，prim算法是求一个所有边都是最小的树，即最小生成树，用集合来维持这个树，所以是到…

n表示点的数量， m表示边的数量，当m和n^2 相近时是稠密图，当m和n相近时是稀疏图，用的是堆优化版的dijkstra算法最短路算法的难点在建图无向图是特殊的有向图，所以在最短路的算法当中，可以用有向图的算法来直接解决无向图的最短路问题朴素dijkstra基本思路定义一个int数组dist[]，表示每个点到原点的距离，定义一个bool数组st[]…

树是无环连通图图分为两种，一种是有向图例如a -> b 另外一种是无向图，a-b。有向图就是记录从a到b的路径，无向图就是从a 到b可以，b到a也行，所以在存储无向图的时候就是存两个有向图，分别是a -> b 和 b -> a。存储有向图的方法有两个一个是邻接矩阵，就是开一个二维数组，表示从a 到 b的边，如果存在存1，不存在存0…

bfs就是宽度优先搜索，用到队列来保持一个先入先出的结构，队列开的长度应该是边长的平方表示的是全部点的个数，存的是位置，所以可以是用pair<int, int> 来存，其中用组数模拟队列的方法就是定义两个指针，hh、tt ,hh = 0, tt = -1,存入元素时，++tt ,表示向后退一格，弹出队头时hh++，表示同时退后一个元素，…

在算法竞赛中，堆常被用来处理需要动态维护最小值或最大值的操作。本文介绍一种基于最小堆的数据结构，支持插入、删除、修改和查询最小值的操作，并且针对每个插入操作进行编号，以便实现按插入顺序删除和修改的功能。题目描述我们需要维护一个集合，初始时集合为空，支持如下几种操作：I x，插入一个数 x；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（…

在这篇文章中，我们将深入探讨两个常见的基础算法概念：递归 和 并查集。这两者在计算机算法中非常重要，理解它们的核心思想和应用场景将极大地帮助你解决许多常见的问题。递归的核心思想什么是递归？递归是一种算法思想，它通过函数调用自身来实现重复操作。每次递归调用时，问题的规模都会逐步减小，直到满足特定的条件（基准条件，base case）来结束递归。递归与…