【HDU 4547 CD操作】LCA问题 Tarjan算法-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

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

简介: 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4547 题意:模拟DOS下的cd命令,给出n个节点的目录树以及m次查询,每个查询包含一个当前目录cur和一个目标目录tar,返回从cur切换到tar所要使用的cd命令次数: 注意这里的cd命令是简化版,只能进行如下两种操作:   1.

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

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

注意这里的cd命令是简化版,只能进行如下两种操作:

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

  2. cd   cur\一系列目录\tar                 //由当前目录跳转到目标目录,注意中间的“一系列目录”不能包含父目录..,也就是说,自底向上必须一步步走,而自顶向下可以一步到位

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

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

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

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

这道题还有些细节问题需要处理好:

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

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

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

 这里又了解到了map一个用法,即对[]的重载:对于map<string, int> m,如果调用一次m[s],而s在m中不存在时,会自动插入s并将它的value置为0。这个设计对于这道题很合适,可以维护全局计数变量seq_num,如果返回0的话,分发下一个序号给它即可。

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <vector>
  4 #include <map>
  5 #include <string>
  6 #include <cstring>
  7 using namespace std;
  8 const int MAX_N = 100005;
  9 const int MAX_M = 100005;
 10 
 11 int vis[MAX_N];
 12 int ans[MAX_N];
 13 int ans_tar[MAX_N];//每组查询的目标目录
 14 int indeg[MAX_N];
 15 int depth[MAX_N];
 16 map<string, int> name;
 17 vector<int> G[MAX_N];//邻接表,边不带权
 18 vector<int> query_tar[MAX_N];
 19 vector<int> query_id[MAX_N];
 20 int par[MAX_N];
 21 
 22 int T;
 23 int n, m;
 24 int seq_num;//目录名的序列号,从1开始
 25 
 26 void init(){
 27     seq_num = 1;
 28     memset(vis, 0, sizeof(vis));
 29     memset(ans, 0, sizeof(ans));
 30     memset(ans_tar, 0, sizeof(ans_tar));
 31     memset(indeg, 0, sizeof(indeg));
 32     memset(depth, 0, sizeof(depth));
 33     name.clear();
 34     for(int i=0; i<MAX_N; i++){
 35         G[i].clear();
 36         query_tar[i].clear();
 37         query_id[i].clear();
 38         par[i] = i;
 39     }
 40 }
 41 int find(int x){
 42     return par[x]==x ? x : par[x] = find(par[x]);
 43 }
 44 void unite(int x, int y){
 45     x = find(x);
 46     y = find(y);
 47     if(x==y) return ;
 48     par[y] = x;
 49 }
 50 
 51 void dfs(int r, int l){
 52     //cout << "dfs " << r << endl;
 53     vis[r] = 1;
 54     depth[r] = l;
 55     for(int i=0; i<G[r].size(); i++){
 56         //cout << G[r][i] << endl;
 57         if(vis[G[r][i]]) continue;
 58         dfs(G[r][i], l+1);
 59         unite(r, G[r][i]);
 60     }
 61     for(int i=0; i<query_tar[r].size(); i++){
 62         if(!vis[query_tar[r][i]]) continue;
 63         int cur, tar;
 64         int ans_id = query_id[r][i];//这一查询所持的序列号
 65         int real_tar = ans_tar[ans_id];//这一个查询真正指定的target
 66         if(r == real_tar){//当前r是目标
 67             cur = query_tar[r][i];
 68             tar = real_tar;
 69         }else{//已访问过的那个点是目标
 70             cur = r;
 71             tar = real_tar;
 72         }
 73         //cout << "query " << cur << tar << endl;
 74         int ca = find(query_tar[r][i]);
 75         if(tar == ca) ans[ans_id] = depth[cur] - depth[ca];
 76         else if(cur == ca) ans[ans_id] = 1;
 77         else ans[ans_id] = depth[cur] - depth[ca] + 1;
 78     }
 79 }
 80 
 81 void lca(int r){
 82     //cout << "root " << r << endl;
 83     dfs(r, 0);
 84 }
 85 
 86 int main()
 87 {
 88     freopen("4547.txt", "r", stdin);
 89     scanf("%d", &T);
 90     while(T--){
 91         init();
 92         scanf("%d%d", &n, &m);
 93         for(int i=0; i<n-1; i++){
 94             string c, p;
 95             cin>>c;
 96             int u = name[c];//不存在会自动插入并置value为0
 97             if(u==0){
 98                 u = name[c] = seq_num++;
 99             }
100 
101             cin>>p;
102             int v = name[p];
103             if(v==0){
104                 v = name[p] = seq_num++;
105             }
106             G[u].push_back(v);
107             G[v].push_back(u);
108             indeg[u]++;//入度为0的是根目录
109         }
110         // for(map<string, int>::iterator iter = name.begin(); 
111         //     iter != name.end(); iter++){
112         //     cout << iter->first << iter->second << endl;
113         // }
114         for(int i=0; i<m; i++){
115             string cur, tar;
116             cin >> cur >> tar;
117             int u = name[cur];
118             int v = name[tar];
119             query_tar[u].push_back(v);
120             query_tar[v].push_back(u);
121             query_id[u].push_back(i);//tar和id是同步记录的
122             query_id[v].push_back(i);
123             ans_tar[i] = v;//为辨谁是目标目录
124         }
125         for(map<string, int>::iterator iter = name.begin(); 
126             iter != name.end(); iter++){
127             int id = iter->second;
128             if(indeg[id] == 0){
129                 lca(id);
130                 break;
131             }
132         }
133         for(int i=0; i<m; i++){
134             printf("%d\n", ans[i]);
135         }
136     }
137     return 0;
138 }

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章