【问题描述】
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。
皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
【数据输入】
输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
【数据输出】
输出到OUTPUT.TXT文件中。输出文件仅包含一个数，为所求的最少的经费。
输入数据示例 输出数据示例
25
【分析】
分别用f[i][0]表示i点放看守，f[i][1]表示i点不放看守i点被儿子监视，f[i][2]表示i点不放看守i点被父节点监视三个情况下的最小费用。
f[i][0]=所有子节点t的f[t][0],f[t][1],f[t][2]中最小的一个的合+k[i]
f[i][1]=某个子节点放看守+其他节点的f[t][0],f[t][1]中最小的一个的合
f[i][2]=所有子节点的f[t][1]的合
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 1510
4: #define MAXINT 10000000
5: using namespace std;
6:
7: int son[maxn][maxn];
8: int m[maxn];
9: int n,x;
10: int k[maxn];
11: int tem[maxn];
12: bool ro[maxn];
13: int v;
14: int f[maxn][3];
15:
16: void dp(int x)
17: {
18: if (f[x][0]) return;
19: for (int i=1;i<=m[x];++i)
20: {
21: int t=son[x][i];
22: dp(t);
23: f[x][0]+=min(f[t][0],min(f[t][1],f[t][2]));
24: f[x][2]+=f[t][1];
25: }
26: f[x][0]+=k[x];
27: memset(tem,0,sizeof(tem));
28: int tot=0;
29: for (int i=1;i<=m[x];++i)
30: {
31: int t=son[x][i];
32: tem[i]=min(f[t][0],f[t][1]);
33: tot+=tem[i];
34: }
35: f[x][1]=MAXINT;
36: for (int i=1;i<=m[x];++i)
37: {
38: int t=son[x][i];
39: if (tot-tem[i]+f[t][0]<f[x][1]) f[x][1]=tot-tem[i]+f[t][0];
40: }
41: }
42:
43: int main()
44: {
45: freopen("guard.in","r",stdin);
46: freopen("guard.out","w",stdout);
47:
48: scanf("%d",&n);
49: for (int i=1;i<=n;++i)
50: {
51: scanf("%d",&x);
52: scanf("%d%d",&k[x],&m[x]);
53: for (int j=1;j<=m[x];++j)
54: {
55: scanf("%d",&son[x][j]);
56: ro[son[x][j]]=1;
57: }
58: }
59: for (int i=1;i<=n;++i)
60: if (!ro[i])
61: {
62: v=i;
63: break;
64: }
65: //for (int i=1;i<=n;++i)
66: //f[i][2]=f[i][1]=MAXINT;
67: dp(v);
68: printf("%d\n",min(f[v][0],f[v][1]));
69: return 0;
70: }
71: