点击打开链接
题目意思: 有一个城市发生了火灾,现在给定一个目标节点,然后给定一序列节点间的关系,然后每一次都从节点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. 根据真实类别绘制散点图:绘制降维后的音频数据的散点图,使用真实类别来标识不同颜色,以便与聚类结果...
android手机应用源码Imsdroid语音视频通话源码.rar
营销计划汇报PPT,市场品牌 推广渠道 产品 营销策略tbb.pptx
JavaScript
JavaScript
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
520表白html5爱心代码
520表白html5爱心代码 一个简单的HTML5和CSS代码示例,用于创建一个动态的爱心形状,并在网页上展示一个类似520表白的消息。这个示例使用了CSS的动画效果和HTML的结构。
智慧养老社区方案.pdf
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
JavaScript
codeviz 1.0.12
JavaScript
JavaScript
JavaScript
JavaScript
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
移动应用Android 实现QQ好友列表源码.rar
蛋白质是生物体中普遍存在的一类重要生物大分子,由天然氨基酸通过肽键连接而成。它具有复杂的分子结构和特定的生物功能,是表达生物遗传性状的一类主要物质。 蛋白质的结构可分为四级:一级结构是组成蛋白质多肽链的线性氨基酸序列;二级结构是依靠不同氨基酸之间的C=O和N-H基团间的氢键形成的稳定结构,主要为α螺旋和β折叠;三级结构是通过多个二级结构元素在三维空间的排列所形成的一个蛋白质分子的三维结构;四级结构用于描述由不同多肽链(亚基)间相互作用形成具有功能的蛋白质复合物分子。 蛋白质在生物体内具有多种功能,包括提供能量、维持电解质平衡、信息交流、构成人的身体以及免疫等。例如,蛋白质分解可以为人体提供能量,每克蛋白质能产生4千卡的热能;血液里的蛋白质能帮助维持体内的酸碱平衡和血液的渗透压;蛋白质是组成人体器官组织的重要物质,可以修复受损的器官功能,以及维持细胞的生长和更新;蛋白质也是构成多种生理活性的物质,如免疫球蛋白,具有维持机体正常免疫功能的作用。 蛋白质的合成是指生物按照从脱氧核糖核酸(DNA)转录得到的信使核糖核酸(mRNA)上的遗传信息合成蛋白质的过程。这个过程包括氨基酸的活化、多肽链合成的起始、肽链的延长、肽链的终止和释放以及蛋白质合成后的加工修饰等步骤。 蛋白质降解是指食物中的蛋白质经过蛋白质降解酶的作用降解为多肽和氨基酸然后被人体吸收的过程。这个过程在细胞的生理活动中发挥着极其重要的作用,例如将蛋白质降解后成为小分子的氨基酸,并被循环利用;处理错误折叠的蛋白质以及多余组分,使之降解,以防机体产生错误应答。 总的来说,蛋白质是生物体内不可或缺的一类重要物质,对于维持生物体的正常生理功能具有至关重要的作用。
二叉树的遍历