Nyoj 20 吝啬的国度[dfs]

2024-06-07 03:58
文章标签 dfs 20 nyoj 国度 吝啬

本文主要是介绍Nyoj 20 吝啬的国度[dfs],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:点击打开链接

开始的时候,思路是有的。就是纯粹的深搜。当然广搜也是可以的。本博客仅讲解深搜用法。

由于这是一棵生成树,所以,从出发点到达每个结点的路径是唯一的。

直接深搜就可以。

需要注意的一点是,每个路径都是无向的。为此在陪送了一次WA。

#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;const int N=100003;
int n,s,ans[N];
vector<int> map[N];int dfs(int s){for(int i=0;i<map[s].size();i++){if(ans[map[s][i]]==-1){//深搜写的很好,但是不是自己写的.ans[map[s][i]]=s;dfs(map[s][i]);}}
}int main()
{
//    freopen("input.txt","r",stdin);int T;scanf("%d",&T);while(T--){CLR(ans,-1);CLR(map,0);int a,b;scanf("%d%d",&n,&s);for(int i=1;i<=n-1;i++){scanf("%d%d",&a,&b);map[a].push_back(b);map[b].push_back(a);}dfs(s);ans[s]=-1;for(int i=1;i<=n;i++){printf("%d%c",ans[i],i==n?'\n':' ');}}return 0;
}

的确,深搜写的很好,不过,自己就是没有写出来。

感觉应该是,对于深搜和回溯理解的不是太深刻,自己写不出的深搜也是在情理之中的。

要多加练习,多写才能自己 写出来。

这篇关于Nyoj 20 吝啬的国度[dfs]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1038103

相关文章

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

nyoj 288 士兵杀敌(五)

一道插线问线离线版的题  复杂度O(n); 代码如下: #include<stdio.h>#include<string.h>const int M = 1000003;const int mod=10003;int num[M];int main(){int n,c,q;scanf("%d%d%d",&n,&c,&q);while(c--){int a,b,x;scan

nyoj 1037 Postscript of Tian Ji racing

一道卡贪心的题。 也算一道改编题。 此题的解法推荐为二分图的最大匹配。 首先将输入数据转换一下,然后将满足题意的一组牌建立条边,最终边的覆盖数即为 LN 最后可得的分数。 然后求出最大匹配即可。 代码如下: #include<stdio.h>#include<string.h>char card[30][5];char s[5];int map[30][30];