【問題描述】
太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛。
皇宮以午門為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望見。大內保衛森嚴，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。
可是陸小鳳手上的經費不足，無論如何也沒法在每個宮殿都安置留守侍衛。
幫助陸小鳳布置侍衛，在看守全部宮殿的前提下，使得花費的經費最少。
【數據輸入】
輸入數據由文件名為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: