Poj 1112 Rebuilding Roads（树形DP+背包）-白红宇

Poj 1112 Rebuilding Roads（树形DP+背包）

阅读量：5253 次

发布时间：2019-06-14

本文共 1958 字，大约阅读时间需要 6 分钟。

题意：给你由N个点构成一颗树，问要孤立出一个有P个节点的子树最少需要删除多少条边。N的范围最大为150

N的范围不大，很容易想到在树上面做背包。把每个节点都看成一个背包，然后把每个儿子节点都看成是一组物品。为什么是一组呢，那是因为假设以儿子为根的节点的子树有S个节点，那么就有S+1种情况，要么将这整棵子树舍弃，要么从这个子树中取1-S个节点。

设f[i][j]为以i为根节点的子树，孤立出以i为根节点，一共含有j个节点的子树最少需要删除的边数（不包括删除i和他父亲的连接的那条边（假设i不是根节点））。

从根节点开始dfs，对于每个节点做一次分组背包，如果不要这颗子树的话分组讨论

不要这个子树f[i][j]:f[i][j] = f[i][j]+1

取这个子树当中的节点 f[i][j] = min(f[i][j-k],f[i.child[a]][k])

所以总的就是f[i][j] = min(f[i][j]+1,min(f[i][j-k],f[i.child[a]][k])

注意最后那颗子树可能不是以原来的root为根的

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #define INPUT_FILE "in.txt"#define OUTPUT_FILE "out.txt"using namespace std;typedef long long LL;const int INF = INT_MAX / 4;void setfile() { freopen(INPUT_FILE,"r",stdin); freopen(OUTPUT_FILE,"w",stdout);}const int maxn = 155;struct Node { int cnt,ch[maxn],p,cc;};Node node[maxn];int N,P,dp[maxn][maxn];void dfs(int now,int sz) { dp[now][1] = 0; for(int i = 0;i < node[now].cnt;i++) { int chid = node[now].ch[i]; dfs(chid,sz); for(int j = sz;j >= 1;j--) { int nret = INF; dp[now][j] = dp[now][j] + 1; for(int k = j-1;k >= 1;k--) { nret = min(dp[chid][k] + dp[now][j-k],nret); } dp[now][j] = min(nret,dp[now][j]); } }} int main() {// freopen("in.txt","r",stdin); while(scanf("%d%d",&N,&P) != EOF) { memset(node,0,sizeof(node)); for(int i = 0;i < N - 1;i++) { int a,b; scanf("%d%d",&a,&b); node[a].ch[node[a].cnt++] = b; node[b].p = a; } int root = 0; for(int i = 1;i <= N;i++) { for(int j = 1;j <= N;j++) { dp[i][j] = INF; } } for(int i = 1;i <= N;i++) { if(node[i].p == 0) { root = i; break; } } dfs(root,P); int ans = dp[root][P]; for(int i = 1;i <= N;i++) { if(i != root) { if(dp[i][P] + 1 < ans) { ans = dp[i][P] + 1; } } } printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/rolight/p/3737553.html

你可能感兴趣的文章