树形DP之个人整理总结.doc

树形DP 第 PAGE 页 Auther: 陈江勇 2008年10月22日 树形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是一样的。 有一些不一样的地方要注意一下： 本程序其实不仅仅针对二叉树，可以是任意的树，删除任意个分支都有算。 #includeiostream #includevector #includelimits 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; }; vectorNODEG[MN]; inline int max(int a,int b) { return ab?a:b; } inline int min(int a,int b) { return ab?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;is;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;iN;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; } 有限电视网络（pku1155 TELE） 题目描述： 有一个电视台要用电视网络转播节目。这种电视网络是一树，树的节点为中转站或者用户。树节点的编号为1~N,其中1为总站，2~(N-M)为中转站，（总站和中转站统称为转发站）N-M+1~N为用户