首页 > 代码库 > poj1463（树形dp）
poj1463（树形dp）
题目链接：http://poj.org/problem?id=1463
题意：有N个点，每两个点至多只有一条边，如果在一个结点上放一个士兵，那他能看守与之相连的边，问最少放多少个兵，才能把所有的边能看守住。
分析：
1、dp[i][0]，表示在结点 i 没放置士兵的情况下，看住以结点 i 为根的子树的所有边所需的最少士兵；
2、dp[i][1]，表示在结点 i 放置士兵的情况下，看住以结点 i 为根的子树的所有边所需的最少士兵。
状态转移：
1、dp[i][0]=∑dp[j][1]，j 是 i 的儿子结点；（根结点不放士兵时，与其相连的边必须由儿子结点来看守，否则会出现两点没有士兵的情况）
2、dp[i][1]=dp[i][1]+∑ ( MIN ( dp[j][0] , dp[j][1] ) )，j 是 i 的儿子结点。 （根结点放士兵时，儿子结点可放可不放）
初始化： d[i][0]=0，d[i][1]=1，i是每一个节点
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 2010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;struct edge{ int next,v; edge(){} edge(int v,int next):v(v),next(next){}}e[N*2];int dp[N][2],head[N],num[N],tot,n;void addedge(int u,int v){ e[tot]=edge(v,head[u]); head[u]=tot++;}void dfs(int u,int fa){ for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dfs(v,u); dp[u][0]+=dp[v][1]; dp[u][1]+=min(dp[v][0],dp[v][1]); }}int main(){ int u,v,m; while(scanf("%d",&n)>0) { tot=0; memset(head,-1,sizeof(head)); for(int i=0;i<=n;i++)dp[i][1]=1,dp[i][0]=0; for(int i=0;i<n;i++) { scanf("%d:(%d)",&u,&m); for(int j=0;j<m;j++) { scanf("%d",&v); addedge(u,v); addedge(v,u); } } dfs(1,-1); printf("%d\n",min(dp[1][0],dp[1][1])); }}
poj1463（树形dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。