进阶指南战略游戏树形DP
【进阶指南】战略游戏【树形DP】
Date：2022.03.29
题意描述：
鲍勃喜欢玩电脑游戏，特别是战略游戏，但有时他找不到解决问题的方法，这让他很伤心。
现在他有以下问题。
他必须保护一座中世纪城市，这条城市的道路构成了一棵树。
每个节点上的士兵可以观察到所有和这个点相连的边。
他必须在节点上放置最少数量的士兵，以便他们可以观察到所有的边。
你能帮助他吗？
例如，下面的树：
只需要放置 1 名士兵（在节点 1 处），就可观察到所有的边。
输入格式
输入包含多组测试数据，每组测试数据用以描述一棵树。
对于每组测试数据，第一行包含整数 N，表示树的节点数目。
接下来 N 行，每行按如下方法描述一个节点。
节点编号：(子节点数目) 子节点 子节点 …
节点编号从 0 到 N−1，每个节点的子节点数量均不超过 10，每个边在输入数据中只出现一次。
输出格式
对于每组测试数据，输出一个占据一行的结果，表示最少需要的士兵数。
数据范围
0<N≤1500,
一个测试点所有 N 相加之和不超过 300650。
输入样例：
4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
输出样例：
1
2
思路：我们发现这题和 很相像，但是有所不同。
我们可以将没有上司的舞会归结为“每条边上至多只选择一个点”，这是最大独立集问题；而这题归结为“每条边上至少选择一个点”。因此状态定义时两题相差无异：
f [ u ] [ 0 ] : f[u][0]:
f
[
u
]
[
0
]
: 以
u u
u 为根的子树，不在
u u
u 结点放士兵时，这个子树上最小花费士兵数。
f [ u ] [ 1 ] : f[u][1]:
f
[
u
]
[
1
]
: 以
u u
u 为根的子树，在
u u
u 结点放士兵时，这个子树上最小花费士兵数。
状态转移：
f [ u ] [ 0 ]
∑ j
0 x f [ j ] [ 1 ] ; f[u][0]=\sum_{j=0}^xf[j][1];
f
[
u
]
[
0
]
=
∑
j
=
0
x
f
[
j
]
[
1
]
;
【即边u->j上已确定u处无士兵，为了满足前提j处必须放士兵。其中x是u的所有子结点数量。】
f [ u ] [ 1 ]
∑ j
0 x m i n ( f [ j ] [ 1 ] , f [ j ] [ 0 ] ) + 1 ; f[u][1]=\sum_{j=0}^xmin(f[j][1],f[j][0])+1;
f
[
u
]
[
1
]
=
∑
j
=
0
x
m
i
n
(
f
[
j
]
[
1
]
,
f
[
j
]
[
0
]
)
1
;
【因让每个子树都是最小，加和才最小。此外别忘了u本身也有一个兵要加上。】
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
typedef long long LL;
int n,m,t,f[N][3],fa[N],ans;
int h[N],ne[N],e[N],w[N],idx;
void add(int x,int y)
{
e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}
void dfs_down(int u)
{
f[u][1]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
dfs_down(j);
f[u][1]+=min(f[j][0],f[j][1]);
f[u][0]+=f[j][1];
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(fa,0,sizeof fa);
memset(h,-1,sizeof h);
memset(f,0,sizeof f);//注意每次清空一下，或者可以在dfs中每次都给f[u][0]=0和f[u][1]=1【因为这里只向下递归，每次赋值都相当于给以u为根的子树的两种状态初始化】。
idx=0;
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d:(%d)",&a,&b);
for(int j=1;j<=b;j++)
{
int x;scanf("%d",&x);
add(a,x);fa[x]=a;
}
}
int root=0;//注意点编号从0开始
while(fa[root]>0) root++;
dfs_down(root);
printf("%d\n",min(f[root][0],f[root][1]));
}
return 0;
}