首页 > 代码库 > Vijos1144小胖守皇宫【树形DP】

Vijos1144小胖守皇宫【树形DP】

2024-09-02 21:10:04   217人阅读

皇宫看守

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。
皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入格式：

输入数据由文件名为Guard.in的文本文件提供。输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0<i<=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。

输出格式：

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

样例输入：

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

样例输出：

25

树形动规题，对每个节点开f[2][2]表示状态下的，
f[1][1]表示该节点有人，能守卫；f[0][1]表示该节点无人，但能被子节点守卫；f[0][0]表示该节点无人，不能被子节点守卫；f[1][0]无意义。
然后动规：f[0][0]=∑子节点f[0][1];
f[1][1]=∑子节点三个状态中最小的一个；
f[0][1]=保证子节点中至少有一个有人的状态下子节点的f[1][1]与f[0][1]的累加（f[0][0]不能算进去，因为该节点及其子节点均无人）
 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 struct node{
 5     int size,son[21],f[2][2],w;///f[GuardPresence][Guarded]
 6 }T[1501];
 7 int n;
 8 bool havef[1501];
 9 inline void dfs(int x)
10 {
11     for(int i=1;i<=T[x].size;i++)
12     {
13         dfs(T[x].son[i]);
14         T[x].f[0][0]+=T[T[x].son[i]].f[0][1];
15         T[x].f[1][1]+=min(T[T[x].son[i]].f[0][0],min(T[T[x].son[i]].f[1][1],T[T[x].son[i]].f[0][1]));
16     }
17     T[x].f[1][1]+=T[x].w;
18     int tmp=200000000,p=0;
19     bool flag=false;
20     for(int i=1;i<=T[x].size;i++) if(T[T[x].son[i]].f[1][1]<=T[T[x].son[i]].f[0][1]){flag=true;break;}
21     if(!flag)
22     {
23         for(int i=1;i<=T[x].size;i++) if(tmp>T[T[x].son[i]].f[1][1]-T[T[x].son[i]].f[0][1])
24         {
25             tmp=T[T[x].son[i]].f[1][1]-T[T[x].son[i]].f[0][1];
26             p=i;
27         }
28         T[x].f[0][1]+=T[T[x].son[p]].f[1][1];
29         for(int i=1;i<=T[x].size;i++) if(i!=p) T[x].f[0][1]+=T[T[x].son[i]].f[0][1];
30     }
31    else for(int i=1;i<=T[x].size;i++)T[x].f[0][1]+=min(T[T[x].son[i]].f[0][1],T[T[x].son[i]].f[1][1]);
32     return;
33 }
34 int main()
35 {
36     int num;
37     T[0].f[1][1]=T[0].f[1][0]=100000000;
38     scanf("%d",&n);
39     for(int i=1;i<=n;i++)
40     {
41         scanf("%d",&num);
42         scanf("%d%d",&T[num].w,&T[num].size);
43         for(int j=1;j<=T[num].size;j++)
44         {
45             scanf("%d",&T[num].son[j]);
46             havef[T[num].son[j]]=1;
47         }
48     }
49     int root;
50     for(int i=1;i<=n;i++) if(havef[i]==0){root=i;break;}
51     dfs(root);
52     printf("%d",min(T[root].f[1][1],T[root].f[0][1]));
53     return 0;
54 }

 

Vijos1144小胖守皇宫【树形DP】


联系
我们