皇宫看守(树形dp)

发布于:2021-06-11 00:43:20

Description


太*王世子事件后,陆小凤成了皇上*傅挠耙黄肥涛馈?
皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。?
可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。?


Input


帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。


Output


输入文件中数据表示一棵树,描述如下:?
第1行 n,表示树中结点的数目。?
第2行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i(0对于一个n(0 < n<=1500)个结点的树,结点标号在1到n之间,且标号不重复。?


SampleInput


输出文件仅包含一个数,为所求的最少的经费。

Sample Output


6

1 30 3 2 3 4

2 16 2 5 6

3 5 0

4 4 0

5 11 0

6 5 0


Hint


25


?


分析:考虑到树的特性:每一个点只和它的父亲和儿子有关系,又是求最优方案,所以我们考虑用dp来做。要求只考虑节点为i的树的最佳方案Vi,只需要看他是否被选即可。即VI=min(VI1,VI2) (2表示不选,1表示选)。


F[i]=min(f[I,1],f[I,2]);


F[I,1]=w[i]+∑min(f[j],∑min(f[k,1],f[k,2]))


F[I,2]=∑f[j]; 若所有f[j]

?(j为i的每个儿子,k为j的儿子)


边界条件:


f[i]=f[I,1]


f[I,1]=w[i]


f[I,2]=maxlongint;


答案为min(f[root],f[root,2])


主要程序:


procedure dfs(r:longint);?

var?

??i,j,k:longint;?

??c,t,ii:longint;?

begin?

??v[r]:=false;?

??if a[r,0]=0?

????then?

??????begin? {边界}

??????? f[r,0]:=w[r];? //f[r,0]即为上面的f[r]

??????? f[r,1]:=0;?

????????f[r,2]:=w[r];?

????????exit;?

??????end;?

??for i:=1 to a[r,0] do?

????if v[a[r,i]] then dfs(a[r,i]);?

??t:=0;?

??for i:=1 to a[r,0] do?

????begin?

??????c:=a[r,i];?

??????t:=t+min(f[c,0],f[c,2]);?

????end;?

??f[r,2]:=maxlongint;?

??ii:=t;?

??for i:=1 to a[r,0] do?

????begin?

??????c:=a[r,i]; ?

??????f[r,0]:=f[r,0]+min(min(f[c,0],f[c,1]),f[c,2]);? {状态转移方程}

????? f[r,1]:=f[r,1]+min(f[c,0],f[c,2]);?

??????t:=t-min(f[c,0],f[c,2])+f[c,0];?

??????f[r,2]:=min(f[r,2],t);?

??????t:=ii;?

????end;?

??f[r,0]:=f[r,0]+w[r];?

end;?

??

?

相关推荐

最新更新

猜你喜欢