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;
}