M_sea

洛谷2015 二叉苹果树
Luogu算法很明显是一道树形DP。那么根据套路,设$f[i] [j]$表示以i为根的子树留下j根枝能留住的最多苹...
扫描右侧二维码阅读全文
05
2017/10

洛谷2015 二叉苹果树

Luogu

算法

很明显是一道树形DP。

那么根据套路,设$f[i] [j]$表示以i为根的子树留下j根枝能留住的最多苹果。
然后对于每个节点,枚举k,代表这里剪掉的枝数。
然后状态转移:

$$f[i][j]=max(f[i][j],f[i][j-k]+f[son_i][k-1]+这条边的苹果数)$$

答案即为$f[1] [q]$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
struct Edge //邻接表
{
    int v,w,nxt;
    Edge() { this->v=this->w=this->nxt=0; }
}e[110];
int head[110],cnt=0;
int f[110][110]; //DP用
int n,q;
inline void addEdge(int u,int v,int w) //添加边,注意是无向边
{
    cnt++;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    cnt++;
    e[cnt].v=u;
    e[cnt].w=w;
    e[cnt].nxt=head[v];
    head[v]=cnt;
}
inline int DP(int now,int last) //DP,返回值为子树能剪掉的枝数
{
    int rt=0;
    for (re int i=head[now];i;i=e[i].nxt) { //循环子节点
        int s=e[i].v;
        if (s==last) continue; //特判父节点
        rt+=(DP(s,now)+1); //累加
        for (re int j=min(rt,q);j>0;j--) //保留的树枝数
            for (re int k=min(j,q);k>0;k--) //剪掉的树枝数
                f[now][j]=max(f[now][j],f[now][j-k]+f[s][k-1]+e[i].w); //状态转移
    }
    return rt;
}
int main()
{
    scanf("%d%d",&n,&q);
    for (re int i=1;i<n;i++) { //输入建图
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
    }
    DP(1,1); //DP
    printf("%d\n",f[1][q]); //输出
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 28 PM

发表评论