【問題描述】
太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)。
皇宮以午門為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望見。大內(nèi)保衛(wèi)森嚴，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。
可是陸小鳳手上的經(jīng)費不足，無論如何也沒法在每個宮殿都安置留守侍衛(wèi)。
幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費的經(jīng)費最少。
【數(shù)據(jù)輸入】
輸入數(shù)據(jù)由文件名為INPUT.TXT的文本文件提供。輸入文件中數(shù)據(jù)表示一棵樹，描述如下：
第1行 n，表示樹中結(jié)點的數(shù)目。
第2行至第n+1行，每行描述每個宮殿結(jié)點信息，依次為：該宮殿結(jié)點標號i（0<i<=n），在該宮殿安置侍衛(wèi)所需的經(jīng)費k，該邊的兒子數(shù)m，接下來m個數(shù)，分別是這個節(jié)點的m個兒子的標號r1，r2，...，rm。
對于一個n（0 < n <= 1500）個結(jié)點的樹，結(jié)點標號在1到n之間，且標號不重復。
【數(shù)據(jù)輸出】
輸出到OUTPUT.TXT文件中。輸出文件僅包含一個數(shù)，為所求的最少的經(jīng)費。
輸入數(shù)據(jù)示例 輸出數(shù)據(jù)示例
25
【分析】
分別用f[i][0]表示i點放看守，f[i][1]表示i點不放看守i點被兒子監(jiān)視，f[i][2]表示i點不放看守i點被父節(jié)點監(jiān)視三個情況下的最小費用。
f[i][0]=所有子節(jié)點t的f[t][0],f[t][1],f[t][2]中最小的一個的合+k[i]
f[i][1]=某個子節(jié)點放看守+其他節(jié)點的f[t][0],f[t][1]中最小的一個的合
f[i][2]=所有子節(jié)點的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: