首页 > 代码库 > uva1292 树形dp
uva1292 树形dp
这题说的是给了一个n个节点的一棵树,然后 你 从 这 棵 树 的 n 个 节点中 选择 尽量少的 点使得 每条边都至少有一个 士兵看守
dp[0][i]+=dp[1][j] dp[1][i]+=min(dp[0][j],dp[1][j]);
#include <iostream>#include <cstdio>#include <algorithm>#include <vector>#include <string.h>using namespace std;const int maxn = 1505;int dp[2][maxn];vector<int>F[maxn];bool use[maxn];void inti(int n){ for(int i=0; i<=n; ++i){ F[i].clear(); } memset(use,false,sizeof(use)); memset(dp,0,sizeof(dp)); for(int i=0; i<n; ++i){ int d,num; scanf("%d:(%d)",&d,&num); for(int i=0; i<num; ++i){ int a; scanf("%d",&a); F[a].push_back(d); F[d].push_back(a); } }}void dfs(int now){ dp[0][now]=0; dp[1][now]=1; use[now]=true; for(int i=0; i<int(F[now].size()) ; ++i){ int to = F[now][i]; if(use[to]) continue; dfs(to); dp[0][now]+= dp[1][to]; dp[1][now]+=min(dp[1][to],dp[0][to]); }}int main(){ int n; while(scanf("%d",&n)==1){ inti(n); int ans=0; for(int i=0; i<n; ++i){ if(use[i]==false){ dfs(i); ans+=min(dp[0][i],dp[1][i]); } } printf("%d\n",ans); } return 0;}
uva1292 树形dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。