点击打开链接
题目意思: 有一个城市发生了火灾,现在给定一个目标节点,然后给定一序列节点间的关系,然后每一次都从节点1开始,问我们从节点1到目标节点共有几条路径,并且最后打印出这些路径。
解题思路: 分序一下复杂度,对于最多有21个节点的解空间树来说,对于这颗树的每一层就是21种情况,最坏的情况是搜索到叶子节点,那么这个时候的时间复杂度是非常大,直接回溯肯定是TLE的,那么我们想到了剪枝,我们知道能够到达目标节点的节点都肯定和目标节点有关联或间接关联,那么我们只要找出这些节点,然后在这些节点里面搜索即可
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 22;
int n , sum , flag;
int G[MAXN][MAXN];//邻接矩阵
int ans[MAXN][MAXN];//记录路径
int vis[MAXN];//标记数组
int mark[MAXN];//存储哪些节点和目标有关联
int tempG[MAXN][MAXN];
//预处理(只有那些和目标节点有关联或间接关联的点才去搜索,那么我们用mark数组将这些点标记为1)
inline void judge(int k){
mark[k] = 1;
for(int i = 1 ; i < MAXN ; i++){
if(tempG[k][i] && mark[i] == 0){
tempG[k][i] = 0;
judge(i);
}
}
}
//输出函数
inline void output(){
for(int i = 0 ; i < sum ; i++){
printf("%d" , ans[i][0]);
for(int j = 1 ; j < MAXN ; j++){
if(ans[i][j])
printf(" %d" , ans[i][j]);
}
printf("\n");
}
printf("There are %d routes from the firestation to streetcorner %d.\n" , sum , n);
}
//递归搜索
void dfs(int k){
if(k == n){ //找到目标节点后就是存储路径,注意是要顺序的存储,因此还要处理一下走的步骤
int t = 0;
int tempsum = 0;
for(int i = 1 ; i < MAXN ; i++){
if(vis[i])
tempsum++;
}
for(int j = 1 ; j <= tempsum ; j++){
for(int i = 1 ; i < MAXN ; i++){
if(vis[i] == j)
ans[flag][t++] = i;
}
}
++sum;//路径加加
++flag;
return;
}
else{
for(int i = 2 ; i < MAXN ; i++){
if(mark[i] && G[k][i] && vis[i] == 0){//如果节点和目标节点有关联
vis[i] = vis[k] + 1;//这里是个技巧,方便找到走了几步
dfs(i);
vis[i] = 0;
}
}
}
}
//主函数
int main(){
int x , y;
int cnt = 1;
while(~scanf("%d" , &n)){
memset(vis , 0 , sizeof(vis));
memset(G , 0 , sizeof(G));
memset(ans , 0 , sizeof(ans));
memset(mark , 0 , sizeof(mark));
sum = 0;
flag = 0;
while(1){
scanf("%d%d" , &x , &y);
if(x == 0 && y == 0)
break;
G[x][y] = 1;//邻接矩阵
G[y][x] = 1;
}
memcpy(tempG , G , sizeof(G));
judge(n);//预处理传入目标节点的值
vis[1] = 1;
dfs(1);
printf("CASE %d:\n" , cnt);
output();
cnt++;
}
return 0;
}
分享到:
相关推荐
7. 获取真实类别:根据文件夹结构获取音频数据的真实类别,例如"ambulance"、"firetruck"和"traffic"等。 8. 根据真实类别绘制散点图:绘制降维后的音频数据的散点图,使用真实类别来标识不同颜色,以便与聚类结果...
ChatGPT4.0知识问答、DALL-E生成AI图片、Code Copilot辅助编程,打开新世界的大门
基于matlab实现DOA 估计和自适应波束形成.rar
基于C++的线程安全容器。.zip
华为数字化转型实践28个精华问答glkm.pptx
本周-综合案例.zip
基于Swift简单易上手的iOS开发框架.zip
liba52-0-32bit-0.7.5+svn613-1.19.x86_64
本次的设计主要是通过对动漫系统开发的背景、现状进行了分析,总结出了本次动漫之家系统开发的意义。根据此次开发的目的和意义,本次的系统开发选择了SSM框架、HTML5以及idea平台来进行动漫之家系统的开发,通过MySQL来进行数据库的开发。通过对整个动漫之家系统进行功能需求的调查研究,通过对此次的系统开发进行可行性的分析。通过实体图模型以及功能结构模型来对本次的系统开发进行了整体的开发。在整个系统开发完毕之后,通过截图说明的方式来进行系统功能的介绍,最后通过系统测试来对本次系统的完整性进行测试,最终通过本次的开发,整个动漫之家系统可以实现很好的运行,起到了为动漫爱好者提供动漫资讯的功能运行。 在前端的系统开发上,主要是为了给动漫爱好者们提供一个在线交流、在线观看动漫、在线购买动漫周边的综合性服务平台。通过这个平台,可以通过注册成为会员后,在动漫内容下进行留言互动来实现更好的动漫交流与观后感的分享,可以提高站内用户对于该网站的使用兴趣。而后台则主要为该动漫之家系统的管理员提供管理服务,后台的管理中,管理员能 关键词:动漫之家;论坛网站;SSM框架;MySQL数据库
基于matlab数字图像处理的黄豆数量识别(GUI界面),基于matlab数字图像处理的黄豆数量识别(GUI界面),基于matlab数字图像处理的黄豆数量识别(GUI界面)
数字化转型数据架构设计方法论及案例qy.pptx
在 Apple Silicon Mac 上入门汇编语言.zip
2024年中国微光夜视相机行业研究报告
liba2ps1-4.14-bp154.2.102.s390x
1222222222222
一个基于C++的IM实现.zip
显示温度和电压测量值在一个LCD屏幕上
ASP娱乐KTV夜场人才招聘信息资源网站源码 PC+WAP.rarASP娱乐KTV夜场人才招聘信息资源网站源码 PC+WAP.rar
基于嵌入式
自用的suno AI作曲插件.zip