HDU 1011 Starship Troopers（星河战队）题解

题目来源：HDU http://acm.hdu.edu.cn/showproblem.php?pid=1011

算法类型：树形DP / 树形背包

通过率：Total Submission(s): 6816   Accepted Submission(s): 1845

题目信息

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Problem Description

You, the leader of Starship Troopers, are sent to destroy a base of the bugs. The base is built underground. It is actually a huge cavern, which consists of many rooms connected with tunnels. Each room is occupied by some bugs, and their brains hide in some of the rooms. Scientists have just developed a new weapon and want to experiment it on some brains. Your task is to destroy the whole base, and capture as many brains as possible.

To kill all the bugs is always easier than to capture their brains. A map is drawn for you, with all the rooms marked by the amount of bugs inside, and the possibility of containing a brain. The cavern’s structure is like a tree in such a way that there is one unique path leading to each room from the entrance. To finish the battle as soon as possible, you do not want to wait for the troopers to clear a room before advancing to the next one, instead you have to leave some troopers at each room passed to fight all the bugs inside. The troopers never re-enter a room where they have visited before.

A starship trooper can fight against 20 bugs. Since you do not have enough troopers, you can only take some of the rooms and let the nerve gas do the rest of the job. At the mean time, you should maximize the possibility of capturing a brain. To simplify the problem, just maximize the sum of all the possibilities of containing brains for the taken rooms. Making such a plan is a difficult job. You need the help of a computer.

Input

The input contains several test cases. The first line of each test case contains two integers N (0 < N <= 100) and M (0 <= M <= 100), which are the number of rooms in the cavern and the number of starship troopers you have, respectively. The following N lines give the description of the rooms. Each line contains two non-negative integers – the amount of bugs inside and the possibility of containing a brain, respectively. The next N - 1 lines give the description of tunnels. Each tunnel is described by two integers, which are the indices of the two rooms it connects. Rooms are numbered from 1 and room 1 is the entrance to the cavern.

The last test case is followed by two -1’s.

Output

For each test case, print on a single line the maximum sum of all the possibilities of containing brains for the taken rooms.

Sample Input

Text
1
2
3
4
5
6
7
8
9
10
11
12
13
5 10
50 10
40 10
40 20
65 30
70 30
1 2
1 3
2 4
2 5
1 1
20 7
-1 -1

Sample Output

Text
1
2
50
7

中文题意描述

你作为星河战队的队长，被派去消灭地下臭虫基地。基地由若干房间和通道组成，整体为树形结构，每个房间有且仅有一条通往入口（1号房间）的路径。

每个房间存在一定数量的臭虫，以及对应的大脑虫价值。每1名士兵可以消灭20只臭虫，攻占房间需要消耗对应数量的士兵。行进规则为：经过房间必须留守士兵清剿，士兵不会重复访问房间。

士兵数量有限，无法攻占所有房间，需要合理选择攻占房间，最大化获取的大脑虫总价值。

解题思路

  1. 房间构成树形结构，访问子节点必须经过父节点，属于树形依赖背包问题；

  2. 每个房间所需士兵数：bug数量 / 20，向上取整；

  3. 通过深度优先搜索遍历所有可行路径，枚举所有合法房间组合，计算士兵消耗与最大价值；

  4. 回溯遍历所有树形分支，剔除士兵不足的方案，保留最优解。

AC代码（Java）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
 * for 杭电 ACM1011
 * @author  718225250
 *
 */
public class Main{	
	
	public static class Cavern{
		
		Integer id;
		int bugs;
		int brains;
		int troopers;
		boolean isPass = false;//是否已经过
		List<Integer> next = new ArrayList<Integer>();
		public Cavern(int id, int bugs, int brains){
			this.id = Integer.valueOf(id);
			this.bugs = bugs;
			this.brains = brains; 
			this.troopers = (bugs%20==0 ? bugs/20 : bugs/20+1);
		}
			
	}
	/**
	 * 获得一次遍历的最大值
	 * @return
	 */
	public static int getMax(){
		int Max =curMax;
		int id = _list.get(_list.size()-1);
		boolean hasNextForPass = false;/*是否还有下一个节点供遍历*/
		for(int i=0;i< _caverns[id].next.size();i++){
			Integer nextId = _caverns[id].next.get(i);
			if(!_caverns[nextId].isPass){
				hasNextForPass = true;
				_list.add(nextId);
				_caverns[nextId].isPass = true;
				Max = getMax();
				_caverns[nextId].isPass = false;
				_list.remove(_list.size()-1);
			}
		}
		if(!hasNextForPass){
			int tempMax = getResult() ;
			if(tempMax > Max){
				curMax = tempMax;
				Max = curMax;
			}
		}
		return Max;
	}
 
	/**
	 * 获得结果
	 * @return
	 */
	
	public static int getResult(){
		int result = 0;
		int tempTrooperNumber = __TrooperNumber;
		int tempResult = 0;
		boolean flag = true;
		for(int i =0; i < _list.size(); i++ ){
			Integer id = _list.get(i);
			if(tempTrooperNumber >= _caverns[id].troopers){
				tempTrooperNumber -= _caverns[id].troopers;
				tempResult += _caverns[id].brains;
			}
			else{
				flag = false;
				break;
			}
		}
		if(flag){
			result = tempResult;
		}else{
			tempResult = 0;
			for(int i =0; i < _list.size(); i++ ){
				Integer id = _list.get(i);
				_list.remove(id);
				tempResult = getResult();
				if(tempResult > result){
					result = tempResult;
				}
				_list.add(id);
			}
		}
		return result;
	}
	
	
	public static int __CavernNumber;
	public static int __TrooperNumber; 
	public static Cavern[] _caverns;
	public static int curMax;
	public static final  List<Integer> _list = new ArrayList<Integer>();
	public static void main(String[] args){
 
		Scanner in=new Scanner(System.in);
		while(true){
			__CavernNumber = in.nextInt();
			__TrooperNumber = in.nextInt();
			if( __CavernNumber < 0 && __TrooperNumber < 0 ){
				break;
			} else if(__CavernNumber == 0 || __TrooperNumber == 0){
				System.out.println(0);
			}
			else{
				_caverns = new Cavern[__CavernNumber];
				for(int i=0;i<__CavernNumber;i++){
					int bugs = in.nextInt();
					int brains = in.nextInt();
					_caverns[i] = new Cavern(i, bugs, brains);
				}
				for(int i=0;i<__CavernNumber-1;i++){
					int m = in.nextInt();
					int n = in.nextInt();
					_caverns[m-1].next.add(n-1);
					_caverns[n-1].next.add(m-1);
				}
				curMax = 0;
				Integer start = Integer.valueOf(0);
				_caverns[0].isPass = true;
				_list.add(start);
				System.out.println(getMax());
			}
		}
		
	}
}

代码说明

  1. Cavern 内部类：存储每个房间的虫子数量、大脑价值、所需士兵、邻接节点及访问状态；

  2. getMax() 递归回溯：深度优先遍历整棵树，枚举所有可行访问路径；

  3. getResult() 价值计算：校验当前路径士兵是否充足，不足则剔除节点递归求解最优解；

4.树形建图：采用双向邻接表存储，遍历过程中通过访问状态去重，避免回路。

版权声明：本文为原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。