赞
踩
题目:P2016 战略游戏
DP - 树形DP
给出一棵树,如果在一个点 x x x 放了一个士兵,该士兵将会覆盖所有与点 x x x 直接相邻的边。求最少放多少个士兵,使得所有边都被覆盖
很简单的一道题,跟P2899 [USACO08JAN]手机网络Cell Phone Network非常相似,只不过改成了覆盖边
对于每个点,我们考虑放不放士兵,所以要开一维去储存是否放士兵的状态
f
[
x
]
[
0
]
f[x][0]
f[x][0] 表示以
x
x
x 为根的子树中,点
x
x
x 不放士兵所需要的最小士兵数量
f
[
x
]
[
1
]
f[x][1]
f[x][1] 则表示以
x
x
x 为根的子树中,点
x
x
x 放士兵所需要的最小士兵数量
转移方程:
f
[
x
]
[
0
]
=
∑
f
[
y
]
[
1
]
f[x][0]=\sum f[y][1]
f[x][0]=∑f[y][1],其中
y
y
y 为
x
x
x 的子节点
f
[
x
]
[
1
]
=
1
+
∑
m
i
n
(
f
[
y
]
[
0
]
,
f
[
y
]
[
1
]
)
f[x][1]=1+ \sum min(f[y][0],f[y][1])
f[x][1]=1+∑min(f[y][0],f[y][1]),因为
x
x
x 到
y
y
y 的边已经被覆盖了,所以点
y
y
y 放不放都没关系
最后答案就是
m
i
n
(
f
[
1
]
[
0
]
,
f
[
1
]
[
1
]
)
min(f[1][0],f[1][1])
min(f[1][0],f[1][1])
PS: 这里点
1
1
1 作为根,其实拿任意一个点做根都可以
代码
#include<cstdio> #include<iostream> #include<vector> using namespace std; const int Maxn=1520,inf=0x3f3f3f3f; vector <int> e[Maxn]; int f[Maxn][2]; int n; inline int read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return s*w; } void dfs(int x,int fa) { f[x][1]=1; for(int i=0;i<e[x].size();++i) { int y=e[x][i]; if(y==fa)continue; dfs(y,x); f[x][1]+=min(f[y][1],f[y][0]); f[x][0]+=f[y][1]; } } int main() { // freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;++i) { int x=read()+1,cnt=read(); // 程序中储存的节点编号是 1~n while(cnt--) { int y=read()+1; e[x].push_back(y); e[y].push_back(x); } } dfs(1,0); printf("%d\n",min(f[1][1],f[1][0])); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。