Ural - 1018 纠结的树型DP...

开始题意看错了...因为样例那个2正好是剩下的树枝又是剪掉的树枝..而我一下子犯傻..题目看成减去Q个树枝..剩下的最多苹果...自挽...

题意是给一颗树...每个枝条上有一些苹果( 可能是0..)..问减去一些边后剩下Q条边苹果最多是多少..

典型的树型DP..

首先是恶心的建树过程....其给出的边都是乱序的..不仅是乱序..前后两点也是任意的...我的处理时先把边都给读了..用mar [ ] [ ] 邻接矩阵来记录两两是否相连..用had [ ] 来记录点是否已经接到了树上...例如先将 had [ 1 ] = true;..然后扫描找与1有边的并且had [ ] 还是 false ( 还没有接到树上去 ) 的点... 将这个点的father置为1...had[ ]置为true...然后入队列...每次就取出队首...反复做这个操作..树就建好了...( 我的建树只需一个father[ ] 指针指向父亲就可以了...以为我的DP只要从叶子一直推上去..)

我有个重要的处理..先把边上的苹果都推到其下方的点上..这样后面DP就直接点的值网上推了...方便思考..当然那么q也要+1...因为两个点才有一个边...

保持从叶子到根..或者说保持孩子做完了自己才做的TOP顺序...就用一个son数组和queue来维持...处理了一个点..就将其father的son--...son为0时入queue....

动规的方程:

temp[i+j]=temp[i+j]>dp[f][j]+value?temp[i+j]:dp[f][j]+value; 其中 value=dp [ h ] [ i ] + apple [ h ] ( h为当前处理的点..这里是通过当前点更新其father ,枚举其father已有的结点数 j 来更新各个情况的值...有点像背包的说..)

dp[ h ] [ i ] ... 代表h点为根时保留了 i 个点..苹果的最大数... 这里用temp而不用dp[ f ] [ i + j ] 是为了避免自己对于自己更新过的重复更新 ( 如用 h 点更新过 1 了...后面有在这个基础上更新了2..显然不对..)....

开始WA得很郁闷..就在网上搜题解...但发现别人和我的方法都不一样...别人的 ： dp[v,i]:=max(dp[v,i],dp[ch[v,1],i]+dp[ch[v,2],l-i-1]+num[v]);

题目给出了是二叉树....别人似乎就是从二叉树出发的...而我这个是完全是无视了这个..树不管是有几个孩子都没管...反正就一直从叶子节点推上去..

囧爆了...后来发现discuss里有人给数据..测出几个Bug..但还是WA...最后自己突然想到一种情况...再交才给AC..不容易啊..

Program:

#include<iostream>
#include<queue>
#define MAXN 200
using namespace std; 
int n,q,k,father[MAXN],apple[MAXN],dp[MAXN][MAXN],son[MAXN],mar[MAXN][MAXN];
bool had[MAXN];
int main()
{ 
    memset(father,0,sizeof(father));  memset(son,0,sizeof(son));
    memset(had,false,sizeof(had));    memset(dp,0,sizeof(dp));
    memset(mar,-1,sizeof(mar));  
    //<特别注意..初始不能为0..因为可能枝上没苹果..但也是枝..两点也是连着的..
    memset(apple,0,sizeof(apple));   
    scanf("%d%d",&n,&q); 
    for (k=1;k<n;k++) 
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        mar[x][y]=mar[y][x]=z; 
    }
    had[1]=true;
    queue<int> myqueue;        
    int h,f,i,j,value,temp[MAXN]; 
    while (!myqueue.empty()) myqueue.pop();
    myqueue.push(1);
    while (!myqueue.empty())
    {
         h=myqueue.front();
         myqueue.pop();
         for (i=1;i<=n;i++) 
          if (mar[h][i]>=0 && !had[i])
          {
              father[i]=h;
              son[h]++;
              apple[i]=mar[h][i];
              had[i]=true;
              myqueue.push(i);              
          }     
    } 
    while (!myqueue.empty()) myqueue.pop();
    for (i=1;i<=n;i++) 
      if (!son[i]) myqueue.push(i); 
    while (1)
    {
          h=myqueue.front();
          myqueue.pop();
          if (h==1) break; 
          f=father[h];
          son[f]--;
          if (!son[f]) myqueue.push(f);   
          for (i=1;i<=n;i++) temp[i]=dp[f][i];        
          for (i=1;i<=n;i++) 
          {
              value=dp[h][i]+apple[h];    
              for (j=1;j<=n-i;j++)
                temp[i+j]=temp[i+j]>dp[f][j]+value?temp[i+j]:dp[f][j]+value;
          }
          for (i=1;i<=n;i++) dp[f][i]=temp[i];
    } 
    printf("%d\n",dp[1][q+1]); 
    return 0;   
}