二叉苹果树
题目意思:
有一棵苹果树,苹果树的是一棵二叉树,共N个节点,树节点编号为1~N,编号为1的节点为树根,边可理解为树的分枝,每个分支都长着若干个苹果,现在要要求减去若干个分支,保留M个分支,要求这M个分支的苹果数量最多。
树形DP
将边的值转化成了点的值,方便处理
#include<cstdio> #include<vector> using namespace std; #define Max_(a,b) (a>b?a:b) struct Node{ int v,L; }num[110]; struct Edge{ int x,y,v; }ff[110]; vector<int> cnt[110]; int vis[110],d[110][110]; void DFS(int x,int flag) { int i; num[x].L=flag; vis[x]=1; for(i=0;i<cnt[x].size();i++) { if(!vis[cnt[x][i]]) DFS(cnt[x][i],flag+1); } } void fun(int x,int Q) { if(d[x][Q]!=-1) return ; if(Q==0) { d[x][Q]=0; return ; } if(Q==1) { d[x][1]=num[x].v; return ; } int l,r,i,ok=0; for(i=0;i<cnt[x].size();i++) { if(num[cnt[x][i]].L > num[x].L) { l=cnt[x][i]; break; } } while(++i<cnt[x].size()) { if(num[cnt[x][i]].L > num[x].L) { r=cnt[x][i]; ok=1; } } if(ok) { d[x][Q]=0; for(i=0;i<Q;i++) { fun(l,i); fun(r,Q-i-1); d[x][Q]=Max_(d[x][Q],d[l][i]+d[r][Q-i-1]+num[x].v); } } else d[x][Q]=num[x].v; } int main() { int N,Q; int i; while(scanf("%d%d",&N,&Q)==2) { for(i=1;i<=N;i++) cnt[i].clear(); for(i=1;i<N;i++) { scanf("%d%d%d",&ff[i].x,&ff[i].y,&ff[i].v); cnt[ff[i].x].push_back(ff[i].y); cnt[ff[i].y].push_back(ff[i].x); } memset(vis,0,N*sizeof(vis[0])); DFS(1,0); for(i=1;i<N;i++) { if(num[ff[i].x].L<num[ff[i].y].L) num[ff[i].y].v=ff[i].v; else num[ff[i].x].v=ff[i].v; } memset(d,-1,sizeof(d)); d[0][Q]=0; for(i=0;i<=Q;i++) { fun(cnt[1][0],i); fun(cnt[1][1],Q-i); d[0][Q]=Max_(d[0][Q],d[cnt[1][0]][i]+d[cnt[1][1]][Q-i]); } printf("%d\n",d[0][Q]); } return 0; }