树形DP

算法

树形DP

二叉苹果树(ural 1108)

题目意思：

有一棵苹果树，苹果树的是一棵二叉树，共N个节点，树节点编号为1~N，编号为1的节点为树根，边可理解为树的分枝，每个分支都长着若干个苹果，现在要要求减去若干个分支，保留M个分支，要求这M个分支的苹果数量最多。

输入：

N M

接下来的N-1行是树的边，和该边的苹果数N and M (1 ≤ M < N; 1 < N ≤ 100)

输出：

剩余苹果的最大数量。

input

5 2

1 3 1

1 4 10

2 3 20

3 5 20

output

21

算法：

删除了某个分支，那么这个分支下的子分支也同时删除。

保留M个分支，也就是删除N-M-1个分支。剩余的最多苹果数=总苹果数-剪掉的苹果数。

注意本题给的边并没有按照树根--树叶的形式来给，也没有按照树的顺序给出边。本来想一个节点对应一个分支长着的苹果数量，cost[v]就表示v这个节点的苹果数，可以这样做，但是在输入的时候，不知道这个苹果数量是那个节点的，因为不知道哪个是哪个的子结点。所以用了无向图和苹果数加到边上去。

我的解法中：这题的树状DP的整体思想个pku3345是一样的。

有一些不一样的地方要注意一下：

本程序其实不仅仅针对二叉树，可以是任意的树，删除任意个分支都有算。

#include<iostream>
#include<vector>
#include<limits>
using namespace std;
#define MN 110
int f[2*MN],p[MN],tmp[MN];
int N,M;
bool visit[MN];
struct NODE
{
       int val;
       int cost;
};
vector<NODE>G[MN];
inline int max(int a,int b)
{
       return a>b?a:b;
}
inline int min(int a,int b)
{
       return a<b?a:b;
}
void my_clear()
{
       int i;
       for(i=0;i<=N;i++)
       {
              G[i].clear();
       }
       memset(visit,false,sizeof(visit));
}
int DP(int v,int from)
{
       visit[v]=true;
       int i,j,k,s,w,last,now;
       s=G[v].size();
       if(s==1)  //这边不再是s==0
       {
              p[0]=0;
              return 1;
       }
       last=0;
       f[from]=0;
       for(i=0;i<s;i++)
       {
              w=G[v][i].val;
              if(visit[w]==true)
                     continue;
              now=DP(w,from+last+1);
              p[now]=p[now-1]+G[v][i].cost;  //这边不要漏,把节点w也给删除
              for(j=0;j<=last+now;j++)
                     tmp[j]=INT_MAX;
              for(j=0;j<=last;j++)
              {
                     for(k=0;k<=now;k++)
                     {
                            tmp[j+k]=min(tmp[j+k],f[from+j]+p[k]);
                     }
              }
              last+=now;
              for(j=0;j<=last;j++)
              {
                     f[from+j]=tmp[j];
              }
       }
       for(i=0;i<=last;i++)
              p[i]=f[i+from];
       last++; //加上自身节点
       return last;
}
int main()
{
       int i,a,b,sum,c;
       NODE tmp;
       while(scanf("%d%d",&N,&M)!=EOF)
       {
              sum=0;
              my_clear();
              for(i=1;i<N;i++)
              {
                     scanf("%d%d%d",&a,&b,&c);
                     tmp.cost=c;
                     tmp.val=b;
                     G[a].push_back(tmp);
                     tmp.val=a;
                     G[b].push_back(tmp);
                     sum+=c;
              }
              DP(1,0);
              printf("%d\n",sum-f[N-M-1]);
       }
       return 0;
}