设为首页 加入收藏

TOP

POJ 1470 Closest Common Ancestors LCA题解
2015-07-24 05:36:44 来源: 作者: 【大 中 小】 浏览:5次
Tags：POJ 1470 Closest Common Ancestors LCA 题解

本题也是找LCA的题目，不过要求多次查询，一般的暴力查询就必然超时了，故此必须使用更高级的方法，这里使用Tarjan算法。

本题处理Tarjan算法，似乎输入处理也挺麻烦的。

注意： 因为查询的数据会极大，故此使用一个数组记录所有查询数据就会超时的。我就载在这里了。查了好久才想到这点。因为我使用了一个vector容器记录了查询数据，故此每次都循环这组这么大的数据，就超时了。----解决办法：使用一个vector quest来记录查询数组，这样每次都只需要循环某节点的邻接查询点就可以了，数据量是很小的。

有些说法没道理的：比如：结尾是否有空格？没有！

我使用了按权值查询并查集的优化，实验证明：没有优化效果。

使用map容器记录结果，好像没有加速，不过这样的代码更加成熟。

其他就是Tarjan算法了，网上也不少解说的了，结合代码学习，这个算法也不难。


#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       using namespace std; struct Node { bool notRoot; bool vis; vector
       
         child; }; const int MAX_N = 901; int N, u, v, n; Node Tree[MAX_N]; //vector
        
          quest;//这样记录就会超时，应该是因为需要查询的数据极其大，所以引发超时 vector
         
           quest[MAX_N]; map
          
            ans; int par[MAX_N]; int rank[MAX_N]; int ancestor[MAX_N]; void init(int n) { for (int i = 1; i <= n; i++) { Tree[i].child.clear(); Tree[i].notRoot = false; Tree[i].vis = false; quest[i].clear(); } } int find(int x) { if (!par[x]) return x; return par[x] = find(par[x]); } void unionTwo(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) par[x] = y; else { par[y] = x; rank[x]++; } } void LCATarjan(int r) { //ancestor[r] = r; for (int i = 0; i < (int)Tree[r].child.size(); i++) { int v = Tree[r].child[i]; //if (Tree[v].vis) continue; LCATarjan(v); unionTwo(r, v); ancestor[find(r)] = r; } Tree[r].vis = true; for (int i = 0; i < (int)quest[r].size(); i++) { int v = quest[r][i]; if (Tree[v].vis) ans[ancestor[find(v)]]++; } } int main() { while (scanf("%d", &N) != EOF) { init(N); memset(par, 0, sizeof(int) * (N+1)); memset(ancestor, 0, sizeof(int) * (N+1)); memset(rank, 0, sizeof(int) * (N+1)); for (int i = 0; i < N; i++) { scanf("%d", &u); while (getchar() != '(') ; scanf("%d", &n); while (getchar() != ')') ; for (int j = 0; j < n; j++) { scanf("%d", &v); Tree[u].child.push_back(v); Tree[v].notRoot = true; } } scanf("%d", &n); for (int i = 0; i < n; i++) { char a = getchar(); while (a != '(') a = getchar(); u = 0; a = getchar(); while (a != ' ') { u = (u <<3) + (u<<1) + (a - '0'); a = getchar(); } v = 0; a = getchar(); while (a != ')') { v = (v<<3) + (v<<1) + (a - '0'); a = getchar(); } quest[u].push_back(v); quest[v].push_back(u); } int root = 0; for (int i = 1; i <= N; i++) { if (!Tree[i].notRoot) { root = i; break; } } ans.clear(); LCATarjan(root); map
           
            ::iterator it; for (it = ans.begin(); it != ans.end(); it++) { printf("%d:%d\n", it->first, it->second); } } return 0; }




【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：Codeforces Round #254 (Div. 2) 下一篇：C++学习笔记32 谓词函数

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: