最小生成树
/*1.生成树
2.n点只保留n-1条边，不能存在回路(任意两点只有一条路)
3。权值之和最小，同时保证联通
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/
//队列：
/
借助队列的实现过程：
1.将起始队列染色并加入队列
2.队首节点拿出来，也就是出队，再把原队首周围未染色的节点放入队列并染色。
3。重复第二步，直到队列为空。
queue基本操作：
/
/
空间优化——————一维数组
for(int i=1;i<=n;i++){
for(int j=w[i];j<=c;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
以为优化：
正向遍历
出现重复装载的情况，是完全背包
倒序遍历
不出现重复装载的情况，是01背包
/
/
int tot=0;
for(int i=1;i<=n;i++){
}
/
//-------------------------------------------------
//2026.5.23迷宫模板
//确定回溯关键词：所有路径、不走重复点、多方案枚举。
/
1.确认方向数组
2.vis数组---防止走回头路
void dfs(int x,int y){
if(xfx&&yfy){
处理结果
return ;
}
//枚举所有方向
for(int i=起始位置;i<总范围;i++){
if(合法条件){
标记状态（比如used[i]=true）；
dfs(新状态)
恢复状态(比如used[i]==false);
}
}
}
*/
//-----------------
//集训营
//2026.7.22
//八皇后
}*/
//----------------------------------------
/*深搜
一条路走到头
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y){
for(int i=0;i<4;i++){
int fx=x+dx[i];
int fy=y+dx[i];
bool check=fx>=0&&fx<n&&fy>0&&fy<n;
if(check&&!vis[x][y]&&固定障碍物){
dfs(fx,fy);
}
}
}
*/
//--------------------------------------
/广搜/
/*从起点出发，遍历所有下一层的节点
将起点入队
队列不为空就循环
对手元素出队
遍历
是否可遍历
可访问入队
*/
//DP(Dynamic Programming)动态规划
/*h核心思想：将大问题转换成小问题，保存问题答案，避免重复计算子问题
三要素：
状态：dp数组的含义
转移：表示当前dpi
边界
步骤：
分析问题
定义
写转移方程
定义边界
循环计算
*/
//板子
/
}*/
//----------
/*一.dfs所有板子
板3.最大异或和
*/
算法优化的方法
一般情况下时间复杂度过高，用二分
线性搜索O(n)到O(logn)
2.在计算过程中，题目中如果有重复计算的成分，利用重复计算数据存储的方式解决
例：计算递归计算斐波那契数列——优化递推来进行以及计算数据存储
板子代码（神秘高端逆天难懂前缀和）
洪水：
线性DP
一，递推:当前状态和之前状态之间的关联
递推式：
汉诺塔:f(n)=2f(n-1)+1;
完全错排:f(n)=(n-1)(f(n-1)+f(n-2));
边界:确认之前和的状态关联
背包：
01背包：最值
dp[i][v]:状态前i个武平，最大价值
if(j<w[i]){
dp[i][j]=dp[i-1][j];
}else{
考虑放和不放
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]+v[i]]);
}
最长公共子序列
