[caioj 1114]多叉蘋果樹---樹形dp+01背包

題目描述

有一棵蘋果樹，如果樹枝有分叉，可以是分多叉，分叉數k>=0（就是說兒子的結點數大于等于0）這棵樹共有N個結點（葉子點或者樹枝分叉點），編号為1~~N,樹根編号一定是1。我們用一根樹枝兩端連接配接的結點的編号來描述一根樹枝的位置。下面是一顆有4個樹枝的樹

現在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。給定需要保留的樹枝數量，求出最多能留住多少蘋果。

輸入格式:

輸入第一行包含兩個整數n，k(1<=k 輸入接下來的n – 1行，每一行包含三個整數x，y，c，表示節點x和y之間有一條樹枝。c表示這根樹枝上蘋果的數量。

輸出格式：

輸出一行，為最多可以保留的蘋果數。

Input

6 2

1 3 1

1 4 10

1 6 21

2 3 20

3 5 20

Output

31

資料規模：

對于20%的資料，滿足1 <= n <=15。

對于40%的資料，滿足1 <= n <=100。

對于100%的資料，滿足1 <= n <=310。

輸入

輸出

分析

本題目前有兩種方法，一種是題目自帶的将多叉樹轉二叉樹，在參照＂二叉蘋果樹＂，還有一種類似于＂比賽轉播＂，每層進行01背包

記錄每棵子樹的大小

用目前的孩子v更新f[u][k]

代碼

#include <cstdio>
#include <cstdlib>
#define open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define close fclose(stdin); fclose(stdout); 
using namespace std;

struct Edge
{
    int to;
    int w;
    int nxt;
};
int cnt;
int head[];
Edge edge[];
inline void add(int x,int y,int z)
{
    edge[++cnt]=(Edge){y,z,head[x]};
    head[x]=cnt;
}

int n,m;
int size[];//節點數
int f[][];//子樹i保留j根樹枝的最大值

inline int read()
{
    int k=;
    int sum=;
    char c=getchar();
    for(;'0'>c || c>'9' ;c=getchar())
        if(c=='-') k=-;
    for(;'0'<=c && c<='9';c=getchar())
        sum=sum*+c-'0';
    return sum*k;
}

inline void write(int x)
{
    if(x<) { putchar('-'); x*=-; }
    if(x>) write(x/);
    putchar(x%+'0');
}

inline int max(int x,int y)
{
    return x>y?x:y;
}

inline int min(int x,int y)
{
    return x<y?x:y;
}

inline void dfs(int u,int pre)
{
    size[u]=;//初始化
    for(int i=head[u];i;i=edge[i].nxt)
    if(edge[i].to!=pre)
    {
        int v=edge[i].to;
        dfs(v,u);
        size[u]+=size[v];
        //不可移至循環外，不然會重複計算
        for(int x=min(size[u],m);x;--x)//01背包，注意順序
//枚舉保留孩子枝條的數量
            f[u][x]=max(f[u][x],f[v][y]+f[u][x-y-]+edge[i].w);
            //保證u->v的樹枝保留，故-1
    }
}

int main()
{
    open("1114");

    n=read();
    m=read();
    for(int i=,x,y,z;i<n;++i)
    {
        x=read(); y=read(); z=read();
        add(x,y,z);
        add(y,x,z);
    }
    dfs(,-);
    write(f[][m]);

    close;
    return ;
}