克隆笔记
2026-10-04 15:49:05
发布于：四川
最小生成树
/*1.生成树
2.n点只保留n-1条边，不能存在回路(任意两点只有一条路)
3。权值之和最小，同时保证联通
kruskal算法 选边闭环————从最小开选，避免成环
贪心算法：
策略：把边按权值从小到大排序，选n-1条边，保证不成回路
关键工具：边结构体数组（起点，终点，权值），并查集（压缩）
步骤
1.边结构体数组 存图
2.初始化并查集
3.遍历所有的边：
3.1 加最小生成树
3.2如果起点和终点在一个并查集，continue
prim 从点着手 阔点 稠密
核心思想————贪心
策略 从任一点出发，每次将最短/没被访问过加入生成树，直到全部纳入
关键工具：
邻接矩阵存图：邻接矩阵存图（全职图），所有权值存为无穷大，表示无直接边
距离：重要遍历准备数组，存储是每一个没纳入生成树的顶点到最小生成树的最小距离。
步骤:
1.存图：
1.1 存图，存权值，初始无穷大
1.2选起点，假如选1，d[1]=0；
2.循环n个点（每次纳一点）
2.1 找未被纳入的生成树且最小点为x；
2.2 没有找未被纳入的生成树且d【j】最小的点？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？/
若x==0，说明已找到，返回false
2.3 标记 1，已被纳入
2.4 扫x点和所有边，更新距离，d[y]=min(d[y],a[x][y]);
取x-y的最小值
3.计算结果 如果算全职，累加，就是权值和
prim算法适合稠密图，定点数n<=5000
*/
#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=200005;
int n,m,tr[N];
int find(int x){
if(tr[x]==x) return x;
return tr[x]=find(tr[x]);
}
struct node{
int u,v,w;
}a[M];
bool cmp(node x,node y){
return x.w<y.w;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) tr[i]=i;
for(int i=1;i<=m;i++){
cin>>a[i].u>>a[i].v>>a[i].w;
}
sort(a+1,a+m+1,cmp);
int ans=0,cnt=0;
for(int i=1;i<=m;i++){
int x=a[i].u;
int y=a[i].v;
int z=a[i].w;
if(find(x)!=find(y)){
tr[find(x)] = find(y);
ans+=z;
cnt++;
}
}
if(cnt==n-1){
cout<<ans;
}else{
cout<<"orz";
}
return 0;
}
/
//队列：
/
借助队列的实现过程：
1.将起始队列染色并加入队列
2.队首节点拿出来，也就是出队，再把原队首周围未染色的节点放入队列并染色。
3。重复第二步，直到队列为空。
queue基本操作：
入队：q.push(x)-->将x压入队列末端
出队：q.pop();-->弹出第一个元素
访问队首：q.front();-->最早被压入队列的元素
访问队尾:q.back();-->最后被压入队尾的元素
访问队列空:q.empty();-->队列空时返回true
访问个数:q.size()-->返回队列元素个数
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
//八皇后
#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=200005;
int n,m,tr[N];
int find(int x){
if(tr[x]==x) return x;
return tr[x]=find(tr[x]);
}
struct node{
int u,v,w;
}a[M];
bool cmp(node x,node y){
return x.w<y.w;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) tr[i]=i;
for(int i=1;i<=m;i++){
cin>>a[i].u>>a[i].v>>a[i].w;
}
sort(a+1,a+m+1,cmp);
int ans=0,cnt=0;
for(int i=1;i<=m;i++){
int x=a[i].u;
int y=a[i].v;
int z=a[i].w;
if(find(x)!=find(y)){
tr[find(x)] = find(y);
ans+=z;
cnt++;
}
}
if(cnt==n-1){
cout<<ans;
}else{
cout<<"orz";
}
return 0;
}
}*/
//----------------------------------------
/*深搜
一条路走到头
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);
}
}
}
*/
//--------------------------------------
/广搜/
/*从起点出发，遍历所有下一层的节点
将起点入队
队列不为空就循环
对手元素出队
遍历
是否可遍历
可访问入队
#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=200005;
int n,m,tr[N];
int find(int x){
if(tr[x]==x) return x;
return tr[x]=find(tr[x]);
}
struct node{
int u,v,w;
}a[M];
bool cmp(node x,node y){
return x.w<y.w;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) tr[i]=i;
for(int i=1;i<=m;i++){
cin>>a[i].u>>a[i].v>>a[i].w;
}
sort(a+1,a+m+1,cmp);
int ans=0,cnt=0;
for(int i=1;i<=m;i++){
int x=a[i].u;
int y=a[i].v;
int z=a[i].w;
if(find(x)!=find(y)){
tr[find(x)] = find(y);
ans+=z;
cnt++;
}
}
if(cnt==n-1){
cout<<ans;
}else{
cout<<"orz";
}
return 0;
}
*/
//DP(Dynamic Programming)动态规划
/*h核心思想：将大问题转换成小问题，保存问题答案，避免重复计算子问题
三要素：
状态：dp数组的含义
转移：表示当前dpi
边界
步骤：
分析问题
定义
写转移方程
定义边界
循环计算
*/
//板子
/
*#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int dist[maxn];
int main(){
int a,b;
cin>>a>>b;
queue<int>q;
q.push(a);
dist[a]=0;
while(!q.empty()){
int x=q.front();
q.pop();
if(x==b){
cout<<dist[x];
return 0;
}
if(x+1<maxn&&dist[x+1]==0){
dist[x+1]=dist[x]+1;
q.push(x+1);
}
if(x-1>=0&&dist[x-1]==0){
dist[x-1]=dist[x]+1;
q.push(x-1);
}
if(x*2<maxn&&dist[x*2]==0){
dist[x*2]=dist[x]+1;
q.push(x*2);
}
}
return 0;
}*/
//----------
/*一.dfs所有板子
*#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int dist[maxn];
int main(){
int a,b;
cin>>a>>b;
queue<int>q;
q.push(a);
dist[a]=0;
while(!q.empty()){
int x=q.front();
q.pop();
if(x==b){
cout<<dist[x];
return 0;
}
if(x+1<maxn&&dist[x+1]==0){
dist[x+1]=dist[x]+1;
q.push(x+1);
}
if(x-1>=0&&dist[x-1]==0){
dist[x-1]=dist[x]+1;
q.push(x-1);
}
if(x*2<maxn&&dist[x*2]==0){
dist[x*2]=dist[x]+1;
q.push(x*2);
}
}
return 0;
板3.最大异或和
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int maxn=2e5+5;
int ans,a[maxn];
void dfs(int p,int num,int xsum){
if(num==k){
ans=max(ans,xsum);
return ;
}
for(int i=p+1;i<=n;i++){
dfs(i,num+1,xsum^a[i]);
}
}
int main(){
cin>>n>>k;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum^=a[i];//x=s^y
}
if(k>n-k){
k=n-k;
}else{
sum=0;
}
dfs(0,0,sum);
cout<<ans;
return 0;
}
*/
算法优化的方法
一般情况下时间复杂度过高，用二分
线性搜索O(n)到O(logn)
2.在计算过程中，题目中如果有重复计算的成分，利用重复计算数据存储的方式解决
例：计算递归计算斐波那契数列——优化递推来进行以及计算数据存储
板子代码（神秘高端逆天难懂前缀和）
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
long long a[maxn];
long long x;
long long pre[maxn];
int n,q;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
}
while(q--){
int sum=0;
cin>>x;
int l=0,r=n;
while(l<=r){
int mid=(l+r)/2;
if(pre[mid]<=x){
sum=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<sum<<endl;
}
return 0;
}
洪水：
#include<bits/stdc++.h>
using namespace std;
int mp[50][50],n;
int dx[10]={0,0,-1,1};
int dy[10]={-1,1,0,0};
void dfs(int x,int y){
mp[x][y]=3;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0 && nx<=n+1 && ny>=0 && ny<=n+1 && mp[nx][ny]==0){
dfs(nx,ny);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
dfs(0,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]==0){
cout<<2<<" ";
}else if(mp[i][j]==3){
cout<<0<<" ";
}else{
cout<<1<<" ";
}
}
cout<<endl;
}
return 0;
}
void bfs(int st){
memset(dist,-1,sizeof(dis));
queue<int> q;
dist[st]=0;
q.push(st);
while(!q.empty){
int u=q.front();
q.pop();
for(){
if(dist[v]==-1){
dist[v]=dist[u]+1;
q.push(v);
线性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]]);
}
最长公共子序列
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int a[1010],dp[1010];
int main(){
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
ans=max(ans,dp[i]);
}
}
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个