提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

冲刺蓝桥2022——dfs专项练习题

2023-02-18 16:27:12 时间

?目录

?冲刺蓝桥 距离【第十三届蓝桥杯4月9日省赛】仅剩【08天】 ?

?今日题目：dfs专项（题目来自洛谷，蓝桥练习系统）

?刷题一览

往期文章推荐-------0基础算法系列

排序（十大排序） 高精度算法 从0->1入门双指针 前缀和 二分 位运算 区间合并

碎碎念

dfs,bfs为何放到最前面?万物皆可暴力,蓝桥杯开始也被称之为暴力杯,开始学习暴力算法,等到后面dp不会的时候也可以用暴力求解,蓝桥评分规则:与acm有很大的不同, 它是根据题解代码通过的测试点给分, 所以在不会的时候可以用暴力来进行骗取一定的分数

讲了这么多应该能明白bf算法对于彦祖们临时抱佛脚的重要性了吧

由于我已经写过一篇bfs和dfs, 我们直接进行题目训练 搜索算法dfs和bfs解析(附有例题） 老规矩: 用?来表示题目难度系数

?[求先序排列]

一点基本常识，给你一个后序遍历，那么最后一个就是根

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void beford(string in,string after){
    if (in.size()>0){
        char ch=after[after.size()-1];
        cout<<ch;//找根输出
        int k=in.find(ch);
        beford(in.substr(0,k),after.substr(0,k));
        beford(in.substr(k+1),after.substr(k,in.size()-k-1));//递归左右子树；
    }
}
int main(){
    string inord,aftord;
    cin>>inord;cin>>aftord;//读入
    beford(inord,aftord);cout<<endl;
    return 0;
}

高手去散步

#include<bits/stdc++.h>
using namespace std;
int n,m; 
int mp[25][55];
bool vis[25];
int ans,s;
 
void dfs(int x,int y){//搜索 ，x，y是这两个景点 
	if(vis[y]){//当我们发现这个景点来过时，我们就可以存下答案了 
		jie:
		ans=max(ans,s);	//只存最大的路程 
		return ;//回到上一步看看有没有更优解 
	}
	for(int i=1;i<=n;i++){//遍历数组 
		if(!vis[x]&&mp[y][i]!=0){//如果这个景点我们没有来过，且我们找到了与之联通的点 
			s+=mp[x][y];		//暂存变量s先存下我们走过的路程 
			vis[x]=1;		   //标记我们来过这个景点 
			dfs(y,i);		  //进行递归，将下个联通点存入 
			s-=mp[x][y];
			vis[x]=0;		//回溯 
		}
	}
	for(int i=1;i<=n;i++){//这一部分是针对绝路的，就是这个景点只有一个景点与之相连，到了死路不能往下再走了 
		if(mp[y][i]!=0)	//如果发现不是死路就跳出 
		break;
		else if(i==n){	//遍历完地图发现是死路，s就加上当前走过的路程 
			s+=mp[x][y];
			goto jie;	//直接跳入到 ans的判断中 
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){//将景点与景点之间的距离用一个数组去存 
		int a,b;
		cin>>a>>b;
		cin>>mp[a][b];
		mp[b][a]=mp[a][b];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(mp[i][j]!=0){//如果这个数组不为空就去搜索 
				dfs(i,j);
				memset(vis,0,sizeof(vis));//清空标记 
				s=0;//将暂存变量S清零 
			}
		}
	}
	cout<<ans;
	return 0;
}

相关文章