uva 10243 Fire! Fire!! Fire!!!

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

最小支配集问题啊…..放置最少的点覆盖所有的点。当点数为1输出1

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n;
vector<int>e[N];
int dp[N][2];

void dfs(int u,int fa){
	dp[u][0] = dp[u][1] = 0;
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i];
		if(v == fa) continue;
		dfs(v,u);
		dp[u][0] += dp[v][1];
		dp[u][1] += min(dp[v][0],dp[v][1]);
	}
	dp[u][1]++;
}

int main(){
	while(scanf("%d",&n)!=EOF && n){
		for(int i = 0; i <= n; i++)
			e[i].clear();
		for(int u = 1; u <= n; u++){
			int k,v;
			scanf("%d",&k);
			while(k--){
				scanf("%d",&v);
				e[u].pb(v); 
			}
		}
		if(n == 1) { puts("1"); continue; }
		dfs(1,-1);
		printf("%d\n",min(dp[1][0],dp[1][1]));
	}
	return 0;
}