CJOJ 1976 二叉苹果树 / URAL 1018 Binary Apple Tree（树型动态规划）

Description

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。下面是一颗有 4 个树枝的树。

2 5

\ /

3 4

\ /

1

Input

第1行2个数，N和Q(1<=Q＜= N,1＜N＜=100)。N表示树的结点数，Q表示要保留的树枝数量。

接下来N-1行描述树枝的信息，每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

Output

剩余苹果的最大数量。

Sample Input

5 2

1 3 1

1 4 10

2 3 20

3 5 20

Sample Output

21

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1976

URAL:https://vjudge.net/problem/URAL-1018

Source

树型动态规划

解决思路

我们定义F[u][j]表示以u为根节点的子树保留j条边所能保留的最大苹果数，设v为其子节点。

首先我们想到的状态转移方程是F[u][j]=max(F[u][j],F[v][j-1]+W[u][v])，但是这样方程的意思是这个状态只从子树j转移过来，但这样是不行的。假设u有3个子节点v1,v2,v3，j为5的时候，如果按照上面的方法，就是取F[v1][4],F[v2][4],F[v3][4]中的最大值+这条边上的权值，但F[u][5]还可以从F[v1][1]+F[v2][1]+F[v3][2]再加上这条边上的权值这类转移过来，所以这个转移方程是不对的。

那么我们仍定义F[u][j]表示以u为根节点的子树保留j条边所能保留的最大苹果树，定义v为当前要计算的u的一个子节点，另外定义k-1为从以v为根节点的子树中取k-1条边，那么就从i之前的子节点的子树集合中取j-k条边（因为要满足v中选的边+原来那些点中选的边+1==j，要+1的原因是因为u->j这条边是必选的），再取max即可。

s所以动态转移方程就是F[u][j]=max(F[u][j],F[u][j-k]+F[v][k-1]+W[u][v]);

;最后要注意的就是求上述F[u][j]时循环k的顺序，一定要从大到小，否则会出现重复计算。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

class Edge

{

public:

    int v,w;

};

const int maxN=200;

const int inf=2147483647;

int n,Q;

vector<Edge> E[maxN];

bool vis[maxN];

int F[maxN][maxN]={0};

int dfs(int u);

int main()

{

    int u,v,w;

    cin>>n>>Q;

    for (int i=1;i<n;i++)

    {

        cin>>u>>v>>w;

        E[u].push_back((Edge){v,w});

        E[v].push_back((Edge){u,w});

    }

    memset(vis,0,sizeof(vis));

    dfs(1);

    cout<<F[1][Q]<<endl;

    return 0;

}

int dfs(int u)

{

    int cnt=0;//统计子树枝个数

    vis[u]=1;

    for (int i=0;i<E[u].size();i++)

    {

        int v=E[u][i].v;

        if (vis[v]==0)

        {

            cnt+=dfs(v)+1;//每次要+1，即加上u->v这条边

            for (int j=min(Q,cnt);j>=1;j--)//要取min的原因是要简化循环

                for (int k=j;k>=1;k--)

                {

                    F[u][j]=max(F[u][j],F[u][j-k]+F[v][k-1]+E[u][i].w);

                }

        }

    }

    return cnt;

}