/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,少了个比较明显的优化(主要没想到居然会卡这个优化)*/