TELE （树形DP背包扩展) #by Plato

/problem?id=3017

题意：N个结点的树，有M个叶子结点，取每条边有花费Ci，取每个叶子结点有价值Pi;

求:在保证总收入（总价值-总花费）>0的情况下，能取到的叶子结点的最大数目

Idea:其实就是把背包给扩展到了树结构，通过TreeDP+分组背包来实现。

#include <cstdio>#include <fstream>#include <iostream>#include <cstring>#include <string>using namespace std;#define maxn(x,y) ((x)>(y)?(x):(y))const int INF_MIN = -(1<<28);struct node{int ev,next;};int c[3010],maxn[3010];int N,M;int price[3010];node a[100000];int fa;int head[3010];int f[3010][3010];void Add_edge(int fv,int ev,int cost){fa++;a[fa].ev = ev;c[ev] = cost;a[fa].next = head[fv];head[fv] = fa;maxn[fv]++;}void TreeDp(int fv){int i,k,j,m;if (head[fv] == -1){f[fv][1] = price[fv] - c[fv];return;}for (i = head[fv];i != -1;i = a[i].next){k = a[i].ev;TreeDp(k);maxn[fv] += maxn[k];for (j = maxn[fv];j >= 1;j--)//开始时偷懒，j的范围直接从M->1,结果TLE；后来改成了maxn[fv]；其实也应该，这个循环是在递归中，以前是在main中，调用次数相差很大{for (m = 1;m <= j;m++){f[fv][j] = maxn(f[fv][j],f[fv][j-m]+f[k][m]);}}}for (i = 1;i <= M;i++) f[fv][i] -= c[fv];//f[fv][i] -= c[fv]; 这里也比较坑，样例都改了好久才过，思维不够严密啊}int main(){//freopen("test.txt","r",stdin);int i,j,k,t1,t2;int K;while(~scanf("%d%d",&N,&M)){fa = 0;memset(head,-1,sizeof(head));memset(maxn,0,sizeof(maxn));c[1] = 0;for (i = 1;i <= N-M;i++){scanf("%d",&K);for (j = 1;j <= K;j++){scanf("%d%d",&t1,&t2);Add_edge(i,t1,t2);//Add_edge(j,t1,t2);}}for (i = N-M+1;i <= N;i++)//for (i = 1;i <= M;i++){scanf("%d",&price[i]);}for (i = 0;i <= N;i++){f[i][0] = 0;for (j = 1;j <= M;j++){f[i][j] = INF_MIN;}}TreeDp(1);for (i = M;i >= 0;i--){if (f[1][i] >= 0) break;}printf("%d\n",i);}return 0;}/*code：debug:1st返回WA，估计是输出代码没注释掉；2rd返回LTE，少了个比较明显的优化（主要没想到居然会卡这个优化）*/