NYOJ22-吝啬的国度

2024-03-02 22:18
文章标签 国度 吝啬 nyoj22

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

 

吝啬的国度

时间限制:1000 ms  |  内存限制:65535 KB

难度:3

描述

在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经过的前一个城市是几号城市(假设你不走重复的路)。

输入

第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000),N表示城市的总个数,S表示参观者所在城市的编号
随后的N-1行,每行有两个正整数a,b(1<=a,b<=N),表示第a号城市和第b号城市之间有一条路连通。

输出

每组测试数据输N个正整数,其中,第i个数表示从S走到i号城市,必须要经过的上一个城市的编号。(其中i=S时,请输出-1)

样例输入

1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7

样例输出

-1 1 10 10 9 8 3 1 1 8

来源

经典题目

 

 

 

 

纯吐槽:自己写的总是超时,然后就搜大神的代码。但是发现每一篇代码都一样。要么是vector数组,解决二维数组太大超内存的问题。要么直接是一维数组直接在输入的时候建成有向图。题目解释还都一样,真是搞不懂啊!

这里我就通过别人的解释再用用多组数据测试记录一下对这个问题的理解过程。

 

看别人的代码学到的东西,使用vector数组解决二维数据超内存问题。

              因为给定的城市N的数目太大,建立数组需要用到#include<vector>,vector就是一个不定长数组,vector<int>a就是一个类似于int a[]的整            数数组,只不过他的长度不确定,可以用a.size()读取他的长度。

 

                而vector<int>a[max]就是一个二维数组,只是第一维的大小是固定的(不超过max),二维的大小就不固定了,这道题之所以用到vector            就是利用了他的不定长,如果直接建立二维数组a[n][n],n太大了,这样的二维数组绝对超出内存。

        (1)头文件#include<vector>.

      (2)创建vector对象,vector<int> vec;

      (3)尾部插入数字:vec.push_back(a);

      (4)使用下标访问元素,cout<<vec[0]<<endl;记住下标是从0开始的。

      (5)向量大小:vec.size();

 

 

 

 

剖析题意,从输入数据中可以得到各个城市之间的无向图(因为双向),而我们需要得到的是一个以s城市为起点的有向图。

我们用mp[i]来表示从s到i号城市必须经过的上一个城市编号。

为了更形象的描述,我们在这里 将 mp[a]=b  称为 b指向a  显然,每个节点智能被一个城市指向(否则无法保存嘛)

初始化 mp[i]=0;

则对于每组边的两节点 a,b  

     若mp[b]=0,即无城市指向b,则令a指向b:mp[b]=a

     若mp[b]!=0, 即已经有城市指向b,那么,这时当然要将b指向a,即mp[a]=b;

          然而,我们并不知道是否有城市指向a,若有 则mp[a]!=0 ,上述操作会将此值覆盖

          所以,在此之前,我们需要将所有指向a的城市节点,方向调换,即若t指向a,则改为a指向t

          同时,再以t为起始递归下去,这样就可以让已a为起点的一系列有向线路全部转换方向,实现180转弯。

     经过上述操作我们已经得到一个有向图,但仍然不能满足题目要求,因为起点是s,故每个有向线路的起点必然是由s开始的,

      所以,我们对s点,进行上述的递归操作,此时,任务完成,所有的有向路都是已s点为出发点的了。

 

读了这个解释发现题目给出的数据根本不需要任何变化是吧!搜索函数也没有用上是吧!

那么让我们来举出几组简单的数据测试一下吧!

1
11   1
1     9
1     8
8    10
10   3
8     6
1     2
10   4
9     5
3     7
11   4

发现了吧!这组数据我加入了   11   4 这条路,那么你就会发现10  4  有一条路了。我们的目的是建一条有向路是吧,有向路什么么啊!是不是每个节点的入度必须是1吧!出度是大于等于1吧。我对有向图的理解暂且是这样的(还在不断的学习中)。输入   11   4的时候map[4]=10  说明4已经有爹了怎么办。那么11就不能再当4的爹了吧!如果一个小伙两个爹,世界不就乱套了吗!怎么办,不要怕11只能当孩子了,人家4都长大了也该有孩子了,那就让11叫4爹吧!这也不行啊!你说让人家叫就叫啊!如果11要是个私生子,那人家不就也有爹了吗?对额!那么好的dfs函数终于第一次用上了,看代码B处是吧dfs(a)孙悟空的火眼金睛来了,要看一看11是不是有个不为人知的爹呢!dfs()函数就是火眼金睛啊!一看哇塞map[11]=0  立马发现11没爹就是个石猴啊!来吧就让唐僧(4)收了吧!直接map[11]=4磕头叫爹。

那问题来了,这火眼金睛我也是没搞懂啊

 

if(pre){dfs(pre);   //  Amap[pre]=x;}

 

 

 

这是干嘛的啊!火眼金睛怎能让你们这些小妖看懂那还了得。不过看你这小妖挺勤奋还不坏就偷偷的告诉你吧!悟空天生聪明而且还细心,看到11是个私生子了还没有声张而是偷偷的给11的私生爹做了标记pre就是他爹的名字。哎!有些人只图一时快活随处播种,聪明的悟空是非常了解这种人的,所以悟空怀疑pre也是个私生子,怎么办这也不能直接问人家啊!伤自尊啊!那么就使用必杀技(火眼金睛)吧(dfs(pre))!一看哇塞pre竟然也是个石猴啊!那就让pre给4叫爹吧(这里我要严肃的说一下深搜了dfs,意思是dfs一下如果pre有爹了,不执行map[pre]=x,接着再dfs直到找不到爹再执行map[pre]=x,如果pre没爹了就让map[pre]=x,让pre给x叫爹)

 

 

 

有点复杂啊!捋一捋思路

10   4

11   4

4有爹了不能让11当爹了。

那11有爹吗dfs一下找到11的祖宗是谁。

让11的祖宗管4叫爹就行了(因为11    4是上下辈的关系必须有一个是爹)。

看过家谱的都懂每个人只有一个爹。

 

 

1
11    1
1      9
1      8
8     10
10    3
8      6
2     11
10    4
9       5
3      7
11    4

再来看一个家谱

   2    11

  10    4

   11   4       

怎么办人家11也有爹了,但是2没爹啊,让2 给4叫爹这就不会乱套了

就这样续家谱,自己品味吧!

 

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int map[100001];
void dfs(int x){int pre=map[x];if(pre){dfs(pre);   //  Amap[pre]=x;}	
}
int main()
{int i,n,num,s,a,b;scanf("%d",&n);while(n--){scanf("%d%d",&num,&s);memset(map,0,sizeof(map));for(i=1;i<num;i++){cin>>a>>b;if(!map[b])//如果入度是0就记录那么要不是0就要转到C除操作了吧!map[b]=a;//这里是记录了指向b的a吧  a-->belse{   //  Cdfs(a);  // B   火眼金睛看穿一切map[a]=b;<span style="white-space:pre">	</span>//  别墨迹了磕头叫爹吧!}}adjust(s);map[s]=-1;for(i=1;i<num;i++)printf("%d ",map[i]);printf("%d\n",map[i]);}return 0;
}

 

 

 

 

 

 

 

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



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

相关文章

BZOJ 1006 神奇的国度 弦图最小染色 MCS算法

给定一个弦图,求最小染色 参考cdq的弦图与区间图论文 http://wenku.baidu.com/view/07f4be196c175f0e7cd13784.html http://tieba.baidu.com/p/2891159900 http://www.cnblogs.com/zhj5chengfeng/p/3279649.html

Nyoj 20 吝啬的国度[dfs]

题目链接:点击打开链接 开始的时候,思路是有的。就是纯粹的深搜。当然广搜也是可以的。本博客仅讲解深搜用法。 由于这是一棵生成树,所以,从出发点到达每个结点的路径是唯一的。 直接深搜就可以。 需要注意的一点是,每个路径都是无向的。为此在陪送了一次WA。 #include <cstdio>#include <cstring>#include <stack>#include <v

华硕ROG玩家国度安装Ubuntu20.04,安装过程一直卡着不动,以及快捷键不能用,不能调节键盘亮度等问题的解决办法,另附上安装Ubuntu18.04的方法

华硕ROG玩家国度是一个游戏本,用的硬件都比较新,所以安装Ubuntu18.04、Ubuntu20.04、Ubuntu20.1基本上都会面临一些问题,包括驱动或者安装过程不能进行等问题。 我一共测试了上述三个版本的系统,最终选择了Ubuntu20.04的系统。主要原因是Ubuntu18.04比较旧,不能安装rog的内核驱动,所以rog的快捷键也就无法使用(也有办法解决这些问题,但是比较麻烦!),

NYOJ 题目20吝啬的国度(DFS)

吝啬的国度 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述 在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经过的前一个城市是几号城市(假设你不走重复的路)。   输入 第一行输入一个整数M表示测试数据共有M(1<=

nyoj-20--吝啬的国度-DFS+vector

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=20 #include<stdio.h>#include<string.h>#include<vector>using namespace std;vector<int> G[100005];int s[100005];int vis[100005];void dfs(i

吝啬的国度--无向图,广度优先遍历,内存爆掉了

地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=20 吝啬的国度 时间限制: 1000 ms  |  内存限制: 65535 KB 难度: 3 描述 在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经

3083: 遥远的国度

唔,没初始化 wa了一次… 思路很一眼。 就是说 考虑 树剖 如果 查询点是首都的祖先,那么查询点构成的子树就是 整个树除了 查询点包含 首都的儿子以外所有点。 那么 知道一个子树在树剖上是连续一段区间, 即 现在需要求 出 包含首都的那棵子树的根, 用类似倍增lca的方法即可。 对于查询点不是首都的祖先的情况,答案直接为 查询点这棵子树 的答案 搞定 c++代码如下: #inc

【bzoj3083】【遥远的国度】【树链剖分】

Description 描述 zcwwzdjn在追杀十分sb的zhx,而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时,守护神RapiD阻拦了zcwwzdjn的去路,他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。 问题是这样的:遥远的国度有n个城市,这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都,我们可以把这个首都看做整棵树的根,但

nyoj20 吝啬的国度 (无根树转换为实根树)

题目20 题目信息 运行结果 本题排行 讨论区 吝啬的国度 时间限制: 1000 ms  |  内存限制: 65535 KB 难度: 3 描述 在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经过的前一个城市是几号城市(假设你不走重复的路)。 输入

清明,祭曾经的程序员国度

— 扫描二维码 —加入架构集结群    对技术感兴趣的同学可进群(备注:Java) 怎奈码农们给别人挑BUG的水平太高,几天下来愣是没分出个高下。 这时突然有个激进党领袖跳出来说:『咱别折腾代码了,现在最重要的是生存!如果是我就会在边境修建长城,禁止邻国的产品经理入境,维护国土安全!』 于是这货立马获得了广大码农们的拥戴…… 新的政党上台后,虽说各种语言派系不再随便干架了,但是各种鄙视关系依然