`
128kj
  • 浏览: 601608 次
  • 来自: ...
社区版块
存档分类
最新评论

图的深搜+树状数组练习 POJ 3321(JAVA)

阅读更多
关于树状数组:参看:http://128kj.iteye.com/blog/1743633
POJ3321 题意:
  一棵具有n个节点的树,一开始,每个节点上都有一个苹果。现在给出m组动态的操作:
(C,i)是摘掉第i个节点上面的苹果(若苹果不存在,则为加上一个苹果),(Q,i)是查询以第i个节点为根的子树有几个苹果(包括第i个节点)。

输入是叉之间的关系,

1 2
1 3

就是主干上面两个叉分别是2 和3.


样例:
Sample Input

3    
1 2
1 3
3
Q 1
C 2
Q 1

Sample Output

3
2



分析:
  用树状数组求和,这个数组怎么来定?

从root开始dfs下去记录第一次访问u点时的时间戳为Begin[u](下标),当访问完以u为根的所有子树以后要向上回溯的时候,再记录一个时间戳End[u](下标),这样,这棵树上子树u上的所有苹果和就是Begin[u]到End[u]的区间和,操作就和普通的树状数组一样了~

下面是AC过的代码:
import java.io.BufferedReader;   
import java.io.IOException;   
import java.io.InputStreamReader;   
import java.io.StreamTokenizer;   
import java.util.*; 

public class Main{
         //把苹果树作图处理了。
	private List<ArrayList<Integer>> G;// 邻接表。注:使用邻接矩阵内存溢出。 
	private int k;//顶点数目
	private boolean[] visited;//判断顶点是否被访问过
	private int[] Begin; 
        private int[] End;
        private int Count=0;
        private int Tree[];//树状数组
       

        public Main(int k,List<ArrayList<Integer>> G){
           this.k=k;
           this.G=G;
           visited = new boolean[k+1];
           Begin=new int[k+1];
           End=new int[k+1];
           Tree=new int[k+1];
       }
   
       public int getBegin(int i){
          return Begin[i];
       }
       
       private void cl(){
          for(int i=0;i<=k;i++)
            visited[i]=false;
       }

       private int getEnd(int i){
          return End[i];
       }
       
        public boolean getVis(int i){
          return visited[i];
        }

        private void setVis(int i,boolean fal){ 
               visited[i]=fal;
        }


    private int lowbit(int i) {
      return i&(-i);
   }

   void Update(int i,int Num){
    while(i<= k){
     Tree[i] += Num;
     i += lowbit(i);
   }
  }

 int Sum(int i){
    int sum = 0;
    while(i>0){
     sum += Tree[i];
     i -= lowbit(i);
    }
    return sum;
  }
 public static void main(String[] args) throws IOException{
	 StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));      
          int k;
          sc.nextToken();      
          k = (int) sc.nval;  //顶点数
  
         List<ArrayList<Integer>> G;  
         //构建邻接表
         G = new ArrayList<ArrayList<Integer>>();   
         for(int i = 0;i<=k;i++)   
            G.add(new ArrayList<Integer>());//初始化邻接表   
          for (int i = 1; i <k; i++) {
              sc.nextToken();  
            int u = (int) sc.nval;
               sc.nextToken();  
            int v = (int) sc.nval;
            if(!G.get(u).contains(v)) {//避免重边的情况比如a b可能出现两次的情况   
                G.get(u).add(v);  
                 
           }  
           //对于无向图 
           if(!G.get(v).contains(u)) {
                G.get(v).add(u);  
                 
           }   
	 }
 
         Main ma=new Main(k,G);
          ma.dfs(1);
    
         for(int i = 1;i <= k;i++){
           ma.Update(i,1);
         }
          sc.nextToken();  
          int M=(int) sc.nval;
          ma.cl();
         
        for(int i = 0;i < M;i++){
           sc.nextToken(); 
           String Op=sc.sval;
           sc.nextToken();  
           int Num=(int) sc.nval;
           if(Op.equals("C")){
              if(!ma.getVis(Num))
                ma.Update(ma.getBegin(Num),-1);//摘苹果
              else
                ma.Update(ma.getBegin(Num),1);//长一个
            ma.setVis(Num,!ma.getVis(Num));
          }else if(Op.equals("Q")){
             System.out.printf("%d\n",ma.Sum(ma.getEnd(Num))-ma.Sum(ma.getBegin(Num)-1));
          } 
       }      
    }
     

              
       
     // 深搜
  private void dfs(int v) {
     Begin[v] = ++Count;
      visited[v] = true;
     //System.out.print(v+" ");

   for (int i = 0; i <G.get(v).size(); i++) {   
        //递归调用搜索没有被访问过的当前节点的下一个节点(邻接点)   
     int k=G.get(v).get(i);
     if (!visited[k])   
          dfs(k);   
   }   
    End[v] = Count;
  }

}


源码:
  • 大小: 3.4 KB
0
0
分享到:
评论

相关推荐

    树状数组练习:POJ 2481(JAVA)

    【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...

    图的深搜+回溯练习题:POJ2197

    标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...

    二维树状数组练习 POJ 2029

    它扩展了一维树状数组(也称作线段树),能够处理二维或多维的数组更新和查询操作。在POJ 2029这个题目中,我们可能面临的问题是需要对一个二维矩阵进行动态更新和求和查询,例如计算某一个矩形区域内的元素总和。 ...

    树状数组练习:POJ 3067

    【标题】"树状数组练习:POJ 3067" 树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。...

    深搜+宽搜+剪枝 配合POJ题目

    各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。

    二维树状数组学习之二:练习POJ 1195

    二维树状数组(也称为2D BIT,即二维前缀和)是一种在计算机科学和算法设计中用于高效处理数组更新和查询的数据结构。它在处理矩阵或网格状数据时非常有用,尤其对于需要频繁进行区间求和或者更新的场景。在本篇中,...

    poj 2352 stars(树状数组,线段树)

    ### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...

    ACM常用算法及其相应的练习题.docx

    * 树状树组 + poj1195, poj3321 * RMQ + poj3264, poj3368 * 并查集的高级应用 + poj1703, poj2492 * KMP算法 + poj1961, poj2406 四、搜索 * 最优化剪枝和可行性剪枝 * 搜索的技巧和优化 + poj3411, poj1724

    树状数组题解1

    树状数组,又称线段树(Segment Tree),是一种用于高效解决区间查询与修改问题的数据结构。在上述题目中,树状数组被广泛应用于各种不同的场景,如星星坐标的等级计算、矩阵操作、序列排序优化以及线路交叉点的计算...

    字典树练习 POJ 1056

    标题中的“字典树练习 POJ 1056”是指一个编程问题,源自编程竞赛网站POJ(Programming Online Judge)的题目1056。POJ是一个在线平台,程序员可以在这里提交代码并测试其正确性,以解决给定的问题。这类问题通常...

    凸包练习: POJ 2187(JAVA)

    【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...

    滚动数组应用:POJ 1159

    标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...

    POJ 1751 求最小生成树prim算法(JAVA)

    最小生成树是一棵树形结构,包含了原图的所有顶点,并且其所有边的权重之和最小。 Prim算法的基本思想是从一个起始顶点开始,逐步将与已选顶点集合连接的、具有最小权重的边加入到生成树中,直到所有顶点都被包含。...

    POJ.rar_poj java_poj1048

    【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...

    poj_2682(3).rar_C++ 数组扩充_poj 26_poj 2682_poj26

    "C++ 数组扩充"提示我们问题可能与如何在C++编程语言中处理数组的增长有关,而"poj 26_poj 2682_poj26"似乎是重复提及问题编号,可能是用户在整理文件时的习惯。 描述中提到的“数链思想”可能是指一种处理数组元素...

    树状数组(Binary Indexed Tree)

    **树状数组**(Binary Indexed Tree, BIT),又称**费尼克树**(Fenwick Tree),是一种特殊的数据结构,它能高效地完成对数组元素的累加查询和更新操作。相较于其他数据结构如线段树,树状数组在实现上更为简洁,...

    poj1001java biginteger

    用java的biginteger实现的poj1001,比较简单的方法

Global site tag (gtag.js) - Google Analytics