首页 > 代码库 > 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;}
View Code

 

uva1292 树形dp