HDU 1011 Starship Troopers 树形+背包dp

http://acm.hdu.edu.cn/showproblem.php?pid=1011

 

题意：每个节点有两个值bug和brain，当清扫该节点的所有bug时就得到brain值，只有当父节点被清空时，才可以清扫它          的子节点，而清扫需要一定的人员。给定M个人员，N个结点的树，求最大brain和

 

这看起来是一道非常简单的背包dp

但是

写完提交wa之后，我发现这道题，并不简单！因为他的题意并不是完全和我找到的题意一样（我承认我语文很差劲所以随便找个题解看题意。。），题目中要求每一个人是不能往回走的，所以节点bug值为0时也不能随意收集brain，一个人员只能收集一条链。当然0个人的时候不管怎么样都收集不到brain直接特判。

这个问题可以通过一个非常之骚的操作解决，操作如下

f[a][b]代表以a点为根的子树布置b个人能得到的最大brain的和

for(int k=m;k>=bu[x];k--){
                for(int j=1;j+k<=m;j++){//注意这个地方从1开始
                    f[x][k+j]=max(f[x][k+j],f[x][k]+f[y][j]);
                }
}

j从1开始循环完美避免了不给下面的路分配人却得到brain值的事情发生，然后就可以ac了。。。

但是并没有ac。。为什么呢。。。因为我，没有把写好的清空数据函数放到主程序里。。。

然后我wa了8次。。。引以为戒。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=110;
const double eps=1e-8;
const int modn=45989;
int n,m;
struct nod{
    int next,y;
}e[maxn*2];
int bu[maxn]={},bra[maxn]={},head[maxn]={},tot=0;
bool vis[maxn]={};
int f[maxn][maxn]={};
void init(int x,int y){
    e[++tot].y=y;
    e[tot].next=head[x];
    head[x]=tot;
}
void dfs(int x){
    vis[x]=1;
    int y;
    for(int i=bu[x];i<=m;i++){
        f[x][i]=bra[x];
    }
    for(int i=head[x];i;i=e[i].next){
        y=e[i].y;
        if(!vis[y]){
            dfs(y);
            for(int k=m;k>=bu[x];k--){
                for(int j=1;j+k<=m;j++){
                    f[x][k+j]=max(f[x][k+j],f[x][k]+f[y][j]);
                }
            }
        }
    }
}
void yu(){
    tot=0;memset(f,0,sizeof(f));
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
}
int main(){
    for(;;){
        yu();
        scanf("%d%d",&n,&m);
        if(n==-1||m==-1){
            break;
        }
        for(int i=1;i<=n;i++){
            scanf("%d%d",&bu[i],&bra[i]);
            bu[i]=(bu[i]+19)/20;
        }
        int x,y;
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
            init(x,y);init(y,x);
        }
        if(m==0){
            printf("0
");
            continue;
        }
        dfs(1);
        printf("%d
",f[1][m]);
    }
    return 0;
}