CJOJ 1976 二叉蘋果樹 / URAL 1018 Binary Apple Tree

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=;
const int inf=;

int n,Q;
vector<Edge> E[maxN];
bool vis[maxN];
int F[maxN][maxN]={};

int dfs(int u);

int main()
{
    int u,v,w;
    cin>>n>>Q;
    for (int i=;i<n;i++)
    {
        cin>>u>>v>>w;
        E[u].push_back((Edge){v,w});
        E[v].push_back((Edge){u,w});
    }
    memset(vis,,sizeof(vis));
    dfs();
    cout<<F[][Q]<<endl;
    return ;
}

int dfs(int u)
{
    int cnt=;//統計子樹枝個數
    vis[u]=;
    for (int i=;i<E[u].size();i++)
    {
        int v=E[u][i].v;
        if (vis[v]==)
        {
            cnt+=dfs(v)+;//每次要+1，即加上u->v這條邊
            for (int j=min(Q,cnt);j>=;j--)//要取min的原因是要簡化循環
                for (int k=j;k>=;k--)
                {
                    F[u][j]=max(F[u][j],F[u][j-k]+F[v][k-]+E[u][i].w);
                }
        }
    }
    return cnt;
}