POJ - 1463 Strategic game（树形dp）

题目描述

Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?

Your program should find the minimum number of soldiers that Bob has to put for a given tree.

For example for the tree:

the solution is one soldier ( at the node 1).

Input

The input contains several data sets in text format. Each data set represents a tree with the following description:

the number of nodes

the description of each node in the following format

node_identifier:(number_of_roads) node_identifier1 node_identifier2 … node_identifiernumber_of_roads

or

node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500);the number_of_roads in each line of input will no more than 10. Every edge appears only once in the input data.

Output

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following:

Sample Input

4

0:(1) 1

1:(2) 2 3

2:(0)

3:(0)

5

3:(3) 1 4 2

1:(1) 0

2:(0)

0:(0)

4:(0)

Sample Output

1

2

题目翻译：

Bob非常享受玩电脑游戏的过程，尤其是策略游戏，但是在有些时候，他因为不能在第一时间找到最佳的策略而十分伤心。 现在，他遇到了一个问题。他必须保卫一个中世纪的城市，有很多道路将整个城市连起来，整体上看上去像一棵树。Bob需要放置尽可能少的士兵，保卫树上所有的边。士兵只能放在节点上，但是却可以保卫所有与这个节点相邻的边。

输入格式：

输入包含了多组数据。每组数据用以下的方式描述了一棵树。

第一行包含一个整数n，代表节点总个数。

每一个节点的描述如下：

-节点编号（子树个数）：子树1…子树子树个数

或者

-节点编号（0）.

节点的编号从0到n-1.对于n个（0 < n ≤ 1500）所有的节点而言，每一条边仅在输入数据中出现一次。

输出格式：

每组数据一行，一个整数代表最少放置的士兵个数。

题意：

给出一颗无向树，在树的节点上放战士，这个战士能保卫与他相邻的边，问最少需要多少战士就能把所有的边给保护起来

思路：

每个点都有放士兵和不放士兵两种情况，放士兵的话他通过相邻边所到达的另一个点可以放也可以不放，但是不放士兵的话他通过相邻边所到达的点必须放，咱们可以仿照“没有上司的舞会”那个题来开

数组，f[i][0]表示不选这个点的所有方案的最小值，f[i][1]表示选这个点的所有方案的最小值，具体看代码，实现起来比较容易想

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1510;
int f[N][2];
int h[N],e[N*2],ne[N*2],idx;
void add(int a,int b){
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
void dfs(int u,int fa){
	f[u][0] = 0;
	f[u][1] = 1;
	for(int i=h[u];i!=-1;i=ne[i]){
		int j = e[i];
		if(j == fa) continue;
		dfs(j,u);
		f[u][0] += f[j][1];//他的子节点一定要有
		f[u][1] += min(f[j][0],f[j][1]);//可以有也可以没有
	}
}
int main(){
	int n;
	while(~scanf("%d",&n)){
		memset(h,-1,sizeof h);
		idx=0;
		for(int i=1;i<=n;i++){
			int x,k,y;
			scanf("%d:(%d)",&x,&k);
			while(k--){
				scanf("%d",&y);
				add(x,y);
				add(y,x);
			}
		}
		dfs(0,0);
		int ans = min(f[0][0],f[0][1]);
		cout<<ans<<endl;
	}
	return 0;
}