/*
推荐:四星。
题意:求从消防站到火场路径有多少,并逐个输出
思路:深度搜索,状态存储
结果程序运行超时
可能存在数据,起点和终点不连通,但起点周围是一个稠密图。
这样会导致程序无解,但耗时很大。
如果可以先把那些可以到达终点的节点找出来,再在其中进行搜索就可避免!
解法一:通过深度搜索找出
解法二:通过并查集
解法三:tarjan算法,未解决。。。
*/
//错误代码:
#include <cstdio>
#include <cstring>
bool G[25][25],visit[25];
int path[25],n,res;
void dfs(int k,int cur)
{
if(k==n)
{
res++;
for(int i=1;i<cur;i++)
{
if(i!=1)
printf(" ");
printf("%d",path[i]);
}
printf("\n");
return;
}
for(int i=1;i<=21;i++)
if(G[k][i] && !visit[i])
{
visit[i]=1;
path[cur]=i;
dfs(i,cur+1);
visit[i]=0;
}
}
int main()
{
freopen("data.in","r",stdin);
int cas=1;
while(scanf("%d",&n)==1)
{
int a,b;
res=0;
memset(G,0,sizeof(G));
while(scanf("%d%d",&a,&b)==2)
if(a==0 && b==0)
break;//原来这里漏掉了break,结果导致不按想法输出
else
G[a][b]=G[b][a]=1;
memset(visit,0,sizeof(visit));
path[1]=1;
visit[1]=1;
printf("CASE %d:\n",cas++);
dfs(1,2);
printf("There are %d routes from the firestation to streetcorner %d.\n",res,n);
}
return 0;
}
/*
解法一:深度搜索,使用数组path做存储
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
bool G[25][25],visit[25];
int m,path[25];
int A[25];
int n,fire;
void init(int u)
{
visit[u]=1;
path[m++]=u;
for(int i=1;i<25;i++)
{
if(G[u][i] && !visit[i])
init(i);
}
}
int cmp(const void *a,const void *b)
{
int *pa=(int *)a;
int *pb=(int *)b;
return *pa-*pb;
}
void dfs(int node,int dep)
{
if(node==fire)
{
n++;
for(int i=1;i<dep;i++)
{
if(i!=1)
printf(" ");
printf("%d",A[i]);
}
printf("\n");
return;//error#1:
}
for(int i=0;i<m;i++)
{
if(G[node][path[i]] && !visit[path[i]])
{
visit[path[i]]=1;
A[dep]=path[i];
dfs(path[i],dep+1);
visit[path[i]]=0;
}
}
}
int main()
{
//freopen("data.in","r",stdin);
int u,v,cas;
cas=1;
while(scanf("%d",&fire)==1)
{
memset(G,0,sizeof(G));
while(scanf("%d %d",&u,&v)==2)
{
if(u==0 && v==0) break;
G[u][v]=G[v][u]=1;
}
memset(visit,0,sizeof(visit));
m=0;
init(fire);
qsort(path,m,sizeof(path[0]),cmp);
memset(visit,0,sizeof(visit));
visit[1]=1;
A[1]=1;
n=0;
printf("CASE %d:\n",cas++);
dfs(1,2);
printf("There are %d routes from the firestation to streetcorner %d.\n",n,fire);
}
return 0;
}
/*
解法三:并查集,使用father数组做存储
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
bool G[25][25],visit[25];
int path[25],m;
int A[25];
int father[25];
int n,fire;
int find(int u)
{
return father[u]==u?u:father[u]=find(father[u]);
}
int cmp(const void *a,const void *b)
{
int *pa=(int *)a;
int *pb=(int *)b;
return *pa-*pb;
}
void dfs(int node,int dep)
{
if(node==fire)
{
n++;
for(int i=1;i<dep;i++)
{
if(i!=1)
printf(" ");
printf("%d",A[i]);
}
printf("\n");
return;//error#1:
}
for(int i=0;i<m;i++)
{
if(G[node][path[i]] && !visit[path[i]])
{
visit[path[i]]=1;
A[dep]=path[i];
dfs(path[i],dep+1);
visit[path[i]]=0;
}
}
}
int main()
{
//freopen("data.in","r",stdin);
int u,v;
int cas=1;
while(scanf("%d",&fire)==1)
{
memset(G,0,sizeof(G));
while(scanf("%d %d",&u,&v)==2)
{
if(u==0 && v==0) break;
G[u][v]=G[v][u]=1;
}
for(int i=1;i<25;i++)
father[i]=i;
for(int i=1;i<25;i++)
for(int j=i+1;j<25;j++)
if(G[i][j] &&find(i)!=find(j))
father[find(i)]=find(j);
m=0;
for(int i=1;i<25;i++)
if(find(i)==find(fire))
path[m++]=i;
qsort(path,m,sizeof(path[0]),cmp);
memset(visit,0,sizeof(visit));
visit[1]=1;
A[1]=1;
n=0;
printf("CASE %d:\n",cas++);
dfs(1,2);
printf("There are %d routes from the firestation to streetcorner %d.\n",n,fire);
}
}
分享到:
相关推荐
7. 获取真实类别:根据文件夹结构获取音频数据的真实类别,例如"ambulance"、"firetruck"和"traffic"等。 8. 根据真实类别绘制散点图:绘制降维后的音频数据的散点图,使用真实类别来标识不同颜色,以便与聚类结果...
第五次作业函数第一题--
本项目旨在利用深度学习方法实现作物病害的自动诊断。作物病害是农业生产中的重要问题,及时诊断和处理对于减少产量损失至关重要。 我们采用深度学习算法,通过分析作物的图像,实现对病害的自动识别和分类。项目使用的数据集包括公开的作物病害图像数据集,如ISIC等,并进行了预处理,包括图像增强、分割和特征提取等。 在运行环境方面,我们使用Python编程语言,基于TensorFlow、PyTorch等深度学习框架进行开发。为了提高计算效率,我们还使用了GPU加速计算。此外,我们还采用了Docker容器技术,确保实验结果的可重复性。 项目完成后,将实现对作物病害的快速、准确诊断,为农业生产提供有力支持,有助于减少产量损失。同时,项目成果也可应用于其他图像识别和分类任务。
机械设计CD驱动印刷设备step非常好的设计图纸100%好用.zip
python烟花代码
附件中是一个简单的烟花效果的代码示例: 在Python中,可以使用多种方式来模拟烟花效果,其中一种常用的方法是使用turtle模块,它提供了一个画布和一个小海龟,可以用来绘制各种图形。 这段代码首先导入了turtle模块和random模块,然后在屏幕上绘制了10次烟花爆炸的效果。每次爆炸都是由5个小圆组成,颜色随机选择,圆的大小也是随机的。 请注意,这段代码需要在支持turtle模块的Python环境中运行,并且需要有图形界面的支持。如果你在没有图形界面的环境中(比如某些服务器或者命令行界面),这段代码可能无法正常运行。
商业化产品经理,到底如何实现产品商业化?.docx
Panduit 工业以太网部件内部销售指南
在Java中,实现一个三维装箱(也称为三维背包问题)的算法通常涉及到组合优化和动态规划。这个问题是一个典型的优化问题,其中目标是在三个维度的限制下最大化价值的总和。下面是一个简单的Java代码示例,它使用动态规划来解决三维装箱问题。 请注意,这个代码只是一个简单的示例,它假设所有物品的第三个维度的大小都是1,并且没有给出如何回溯选择物品的完整逻辑。在实际应用中,三维装箱问题可能更加复杂,需要考虑所有三个维度的限制,并且可能需要更复杂的算法来解决。 此外,这个问题的解决方案可能需要根据具体问题的要求进行调整,例如物品是否可以分割、是否允许超过一个的物品等。如果你有特定的问题描述或者需要进一步的帮助,请提供更多的细节。
常用品牌EPLAN部件库
单片机开发的教程可以分为以下几个步骤: 1. 了解单片机基础知识:在学习单片机开发之前,需要了解单片机的相关知识,包括单片机的基本结构、指令系统、编程语言等。 2. 选择开发板:选择一款适合自己学习开发板的型号和厂商,通常需要关注开发板的性价比、开发环境是否友好等因素。 3. 学习开发环境:根据所选的开发板,学习相关的开发环境和使用方法,例如Keil、IAR等集成开发环境。 4. 掌握编程语言:单片机常用的编程语言包括C语言和汇编语言,根据实际情况选择其中一种进行学习。 5. 基础操作:熟悉单片机的引脚定义和IO口配置,了解单片机的启动代码,可以通过修改启动代码进行基本功能调试。 6. 综合实践:根据具体项目需求,进行单片机开发的综合实践。在实践中需要掌握如何编写程序、如何进行硬件调试、如何使用相关工具软件等技能。 下面是一个单片机开发的简单教程介绍: 首先,确定所使用的单片机型号和开发板类型。在这个阶段,需要查阅相关资料,了解开发板的规格书、芯片规格等基本资料。 其次,安装并配置开发环境。根据所选的开发板,安装相应的集成开发环境(IDE),并配置好开发环境。 接着,学习并掌
Q1.ipynb
(自适应手机端)IT网络建站公司pbootcms模板 互联网营销企业网站源码下载.zip
Bematech 激光扫描器用户手册
激励视频接入文档.pdf
java jdk1.8 202版本下载window linux打包
Lite Beam M5快速指南
互联网金融导论.docx
字节跳动青训营——抖音项目
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提高了应用性能,简化了开发流程,并且能更快地响应市场需求。