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