【HDU 2586 How far away?】LCA问题 Tarjan算法

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

题意:给出一棵n个节点的无根树,每条边有各自的权值。给出m个查询,对于每条查询返回节点u到v的最短路径的权值和,按查询顺序输出结果。

数据范围:n [2, 40000], m[1, 200]

思路:Tarjan算法:dfs遍历每个点,每遍历完 r 的一个孩子 c, 把 c 并入以 r 为祖先的集合,并处理 c 的所有查询 q:若qi的目标节点 v 已被遍历到,那么一定有lca(c, v) = find(v)。

具体实现上,需要记录这样几个信息:每个节点的深度depth、邻接表G、访问标记vis。

对于每组查询(u, v)时,可用这个公式得到结果res(u, v) = depth(u) - depth(lca(u,v)) + depth(v) - depth(lca(u,v))。

注意Tarjan算法是脱机的(离线的)、批处理的,即其查询结果的生成顺序与最初的查询输入顺序无关。因此需要将乱序生成的结果合理组织以实现顺序输出。这一点我没有想好怎么做,下面的实现是参照了到网上他人的代码。具体方法就是:用类似记录查询目标节点的方法去记录查询序号,即query[r][i]存的是第r个节点的第i个查询所涉及的目标节点,类似地,num[r][i]存的是第r个节点的第i个查询在输入查询序列中的序号。再附加一个ans[i]存储第i条查询的结果。这样每处理一个查询,即可把结果存入ans[num[r][i]] = res(r, i)

p.s 注意题目描述:没有说节点的序号分布在1...n,而我们的vis, query, depth等数组都是以下标标识节点号访问的。所以每次初始化时注意覆盖到整个区间[1, MAX_N]。这题n<=40000不是很大,若超过数组能开的最大长度,则需要“离散化”。

还有一点就是,这个问题只要使用深度优先遍历策略,左根右三个节点的访问顺序是没有关系的。因此可以借助先序遍历先访问根节点的便利,先修改vis数组,后遍历其邻接表,从而避免因邻接表存了双向边而出现“兜圈子”的情况。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 const int MAX_N = 40005;
  7 const int MAX_M = 205;
  8 
  9 int T;
 10 int n, m;
 11 struct Edge{
 12     int to, cost;
 13     Edge(){}
 14     Edge(int t, int c):to(t), cost(c){}
 15 };
 16 vector<Edge> G[MAX_N];
 17 vector<int> query[MAX_N];
 18 int vis[MAX_N];
 19 vector<int> num[MAX_N];
 20 int par[MAX_N];
 21 int ans[MAX_M];
 22 int depth[MAX_N];
 23 
 24 void init(){
 25     memset(vis, 0, sizeof(vis));
 26     memset(ans, 0, sizeof(ans));
 27     memset(depth, 0, sizeof(depth));
 28     for(int i=0; i<MAX_N; i++){
 29         par[i] = i;
 30         G[i].clear();
 31         num[i].clear();
 32         query[i].clear();
 33     }
 34 }
 35 int find(int x){
 36     if(par[x] == x) return x;
 37     return par[x] = find(par[x]);
 38 }
 39 void unite(int x, int y){
 40     x = find(x);
 41     y = find(y);
 42     if(x == y) return ;
 43     par[y] = x;
 44 }
 45 
 46 void dfs(int r, int l){
 47     vis[r] = 1;//先序遍历
 48     depth[r] = l;
 49     for(int i=0; i<G[r].size(); i++){
 50         if(!vis[G[r][i].to]){
 51             dfs(G[r][i].to, l+G[r][i].cost);
 52             unite(r, G[r][i].to);
 53         }
 54     }
 55     for(int i=0; i<query[r].size(); i++){
 56         if(vis[query[r][i]]){//r的第i个查询的目标节点
 57             int ca = find(query[r][i]);
 58             ans[num[r][i]] = depth[r] + depth[query[r][i]] - depth[ca] - depth[ca]; 
 59         //r的第i个查询所持有的查询号
 60         }
 61     }
 62 }
 63 
 64 void lca(int r){
 65     dfs(r, 0);
 66 }
 67 
 68 int main()
 69 {    
 70     //freopen("2586.txt", "r", stdin);
 71     scanf("%d", &T);
 72     while(T--){
 73         init();
 74         scanf("%d%d", &n, &m);
 75         for(int i=0; i<n-1; i++){
 76             int u, v, c;
 77             scanf("%d%d%d", &u, &v, &c);
 78             G[u].push_back(Edge(v, c));
 79             G[v].push_back(Edge(u, c));
 80         }
 81         for(int i=0; i<m; i++){
 82             int u, v;
 83             scanf("%d%d", &u, &v);
 84             query[u].push_back(v);
 85             query[v].push_back(u);
 86             num[u].push_back(i);//u的下一个查询号插入向量num[u]
 87             num[v].push_back(i);
 88         }
 89         lca(1);
 90         for(int i=0; i<m; i++){
 91             printf("%d\n", ans[i]);
 92         }
 93 //        for(int i=1; i<=n; i++){
 94 //            for(int j=0; j<G[i].size(); j++){
 95 //                printf("%d %d %d\n", i, G[i][j].to, G[i][j].cost);
 96 //            }
 97 //        }
 98     }
 99     return 0;
100 }
上一篇:Hadoop2源码分析-YARN 的服务库和事件库


下一篇:【POJ 1236 Network of Schools】强联通分量问题 Tarjan算法,缩点