【HDU 4547 CD操作】LCA问题 Tarjan算法

  • 时间:
  • 浏览:1
  • 来源:uu快三在线直播 uu快三在线直播 uu快三在线直播

  2. cd   cur\一系列目录\tar                 //由当前目录跳转到目标目录,注意后面 的“一系列目录”非要富含父目录..,也就说 说,自底向上需要一步步走,而自顶向下可能够够 一步到位

  2. else if cur == lca, 则res(cur, tar) = 1;

注意这里的cd命令是多样化版,非要进行如下一种生活生活操作:

  1. if tar == lca,则res(cur, tar) = depth(cur) - depth(lca); (富含tar == cur的状况)

思路:用Tarjan算法求LCA,处理查询需要分类讨论:

 这里又了解到了map另4个 用法,即对[]的重载:对于map<string, int> m,就说 调用一次m[s],而s在m中不所处时,会自动插入s并将它的value置为0。这种设计对于这道题很相当于,可能够够 维护全局计数变量seq_num,就说 返回0搞笑的话,架构设计 下另4个 序号给它即可。

  3. 一点,则res(cur, tar) = depth(cur) - depth(lca) + 1;

这道题还一点细节间题需要处理好:

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4547

1. 每个查询要记录好目标目录是谁。就说 tarjan算法是批处理的,即每完成对另4个 棵子树的遍历,处理其树根所涉及到的查询。为使查询处理不遗漏,大伙把查询也以邻接表的形式存成双向边,然而每次处理需要知道本次查询原始的“单向边”,原来能够根据后面 的分类计算结果。好多好多 我另设了另4个 数组ans_tar[i]记录第 i 个查询所给定的tar。

2. 同HDU2586这道题,多个查询,注意记录查询序列号。这道题我用邻接表项query_id[r][i]记录节点r的第i个查询所持有的查询序列号,用邻接表项query_tar[r][i]记录节点r的第i个查询的目标节点。

  1. cd   ..                                        //返回父目录

3. 给出的目录是字符串,要用另4个 map<string, int>存储名称到节点号的映射关系。

题意:模拟DOS下的cd命令,给出n个节点的目录树以及m次查询,每个查询富含另4个 当前目录cur和另4个 目标目录tar,返回从cur切换到tar所要使用的cd命令次数: