二叉苹果树--树型动态规划T1

来源：JK老班

题目:有一棵苹果树，如果树枝有分叉，一定是分 2 叉（就是说没有只有 1 个儿子的结点）。这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1-N,树根编号一定是 1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝的树：

2 5

\ /

3 4

\ /

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。

程序名：apple

输入格式：

第 1 行 2 个数，N 和 Q(1<=Q<= N,1<N<=100)。

N 表示树的结点数，Q 表示要保留的树枝数量。接下来 N-1 行描述树枝的信息。

每行 3 个整数，前两个是它连接的结点的编号。第 3 个数是这根树枝上苹果的数量。每根树枝上的苹果不超过 30000 个。

输出格式： 一个数，最多能留住的苹果的数量。

输入样例：

5 2

1 3 1

1 4 10

2 3 20

3 5 20

输出样例：

21

来源：URAL(广州六中信息学奥赛小组译)

不能去父留子。

存树，题目没说谁是父亲，谁是孩子，邻接矩阵，邻接链表（数量大时）。

Q=Q左+Q右（Q为边数），Q左：1~Q，Q右：Q-Q左，max{W(Q左)+W(Q右)}。

不从根开始，因为拆下去，会有重复计算。

由叶子往根开始算，树状动态规划，反向层次遍历。

二叉苹果树--树型动态规划T1

import java.util.ArrayList;
import java.util.Scanner;

//邻接矩阵
public class P1559 {

   int N,Q;
   int[][] A;

   public P1559() {

       //输入
       Scanner sc=new Scanner(System.in); N=sc.nextInt(); Q=sc.nextInt();
       A=new int[N+1][N+1];
       for(int i=1;i<=N;i++) //一些树枝上没有苹果，但是树枝是存在的，不能用0表示没有树枝，用-1表示没有树枝。
           for(int j=1;j<=N;j++)
               A[i][j]=-1;

       for(int i=0;i<N-1;i++) {
           int x=sc.nextInt(), y=sc.nextInt(), weight=sc.nextInt();
           A[x][y]=A[y][x]=weight;
       }

       ArrayList[] Children=new ArrayList[N+1];//为了方便，记下孩子
       for(int i=1;i<=N;i++) Children[i]=new ArrayList<Integer>();//每个节点设变长数组，记下孩子

       ArrayList<Integer> Que=new ArrayList<Integer>();//队列
       boolean[] Mark=new boolean[N+1];//已经在队列的点不能再入队，作标记
       Que.add(1); Mark[1]=true;//题目：树根编号一定是1
       int front=0;//队首指针
       while(front<Que.size()) {//当队首指针没越过队尾指针，读队首，看有无孩子，将孩子放入队列
           int head=Que.get(front);front++;
           for(int i=1;i<=N;i++)
               if(A[head][i]!=-1 && Mark[i]==false) {
                   Que.add(i); Mark[i]=true;
                   Children[head].add(i);//加入孩子列表,i是head的孩子
               }
       }
       //for(int a:Que) System.out.print(a+" ");


       //计算
       int[][] Apple=new int[N+1][Q+1];
       for(int i=Que.size()-1;i>=0;i--)//从队尾开始
       {
           int a=Que.get(i);
           if(Children[a].size()!=0) {//非叶节点
               //拿到2个孩子
               int x=(int) Children[a].get(0);
               int y=(int) Children[a].get(1);


               for(int q=1;q<=Q;q++) {
                   int max=0;
                   for(int q1=0;q1<=q;q1++) {//枚举一下左右子树各分多少边
                       int q2=q-q1;
                       int current;
                       if(q1==0)
                           current=Apple[y][q2-1]+A[a][y];//苹果数:左子树不选边，在右子树选q条边，但是要减去父亲连接右子树的那1条边
                       else {
                           current=Apple[x][q1-1]+A[a][x];//苹果数:左子树选q1-1条边(减去父亲连接左子树的那1条边)
                           if(q2>0) current+=Apple[y][q2-1]+A[a][y];//苹果数:加上右子树选q2-1条边(减去父亲连接右子树的那1条边)
                       }

                       if(current>max) max=current;
                   }

                   Apple[a][q]=max;//父亲节点消耗q条边时的苹果数

               }

           }
       }

       System.out.println(Apple[1][Q]);
   }


   public static void main(String[] args) {
       P1559 apple=new P1559();
   }

}

二叉苹果树--树型动态规划T1

相关推荐