poj 1463 (树形dp)

题意：一颗树，n个节点，现在要在节点处设置尽量少的哨兵，使得每条边都被观察到。

思路:dp[v][1] 表示v为根的子树v放哨兵的最小花费。

dp[v][0]表示v为根的子树v不放哨兵的最小花费。

代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 #define MP(a, b) make_pair(a, b)
14 #define PB(a) push_back(a)
15 using namespace std;
16 
17 const int LEN = 2010;
18 vector<int> Map[LEN];
19 int n, dp[LEN][2], ind[LEN];
20 
21 void dfs(int v, int fa){
22     dp[v][0] = 0;dp[v][1] = 1;
23     for(int i=0; i<Map[v].size(); i++){
24         int x = Map[v][i];
25         if(x != fa){
26             dfs(x, v);
27             dp[v][1] += min(dp[x][0], dp[x][1]);
28             dp[v][0] += dp[x][1];
29         }
30     }
31 }
32 
33 int main()
34 {
35   //  freopen("in.txt","r",stdin);
36     //freopen("out.txt","w",stdout);
37     
38     int a, b, tn;
39     while(scanf("%d", &n)!=EOF){
40         for(int i=0; i<LEN; i++) Map[i].clear();
41         memset(dp, 0x3f, sizeof dp);
42         memset(ind, 0, sizeof ind);
43         for(int i=0; i<n; i++){
44             scanf("%d:(%d)", &a, &tn);
45             for(int j=0; j<tn; j++){
46                 scanf("%d", &b);
47                 ind[b] ++;
48                 Map[a].PB(b);
49             }    
50         }
51         int root;
52         for(int i=0; i<n; i++){
53             if(!ind[i]) root = i;
54         }
55         dfs(root, -1);
56         printf("%d
", min(dp[root][0], dp[root][1]));
57     }
58     return 0;
59 }

View Code