poj 1463 Strategic game

题意：给出一个无向图，每个节点只有一个父亲节点，可以有多个孩子节点，在一个节点上如果有一位战士守着，那么他可以守住和此节点相连的边。求最少战士数量。

解法：树形DP的入门级题目。

简单说明：f[i][0]表示以i节点为根没有战士守卫的情况，f[i][1]则表示有战士守卫

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 using namespace std;
 9 const int maxn=1500+10;
10 int n;
11 int father[maxn],vis[maxn],f[maxn][2];
12 void dfs(int root)
13 {
14     vis[root]=1;
15     f[root][1]=1;
16     f[root][0]=0;
17     for (int i=0 ;i<n ;i++)
18     {
19         if (father[i]==root && !vis[i])
20         {
21             dfs(i);
22             f[root][0] += f[i][1];
23             f[root][1] += min(f[i][0],f[i][1]);
24         }
25     }
26 }
27 int main()
28 {
29     while (cin>>n)
30     {
31         int k,a,b;
32         memset(vis,0,sizeof(vis));
33         memset(f,0,sizeof(f));
34         for (int i=0 ;i<n ;i++) father[i]=i;
35         for (int i=0 ;i<n ;i++)
36         {
37             scanf("%d:(%d)",&a,&k);
38             while (k--)
39             {
40                 scanf("%d",&b);
41                 father[b]=a;
42             }
43         }
44         //for (int i=0 ;i<n ;i++)
45         //cout<<i<<" "<<father[i]<<endl;
46         int sum=0;
47         for (int i=0 ;i<n ;i++)
48         {
49             if (father[i]==i)
50             {
51                 dfs(i);
52                 sum += min(f[i][0],f[i][1]);
53             }
54         }
55         cout<<sum<<endl;
56     }
57     return 0;
58 }