https://www.luogu.org/problemnew/show/P2015

二叉蘋果樹

時(shí)間限制:?1 Sec??內(nèi)存限制:?128 MB

題目描述

有一棵蘋果樹，如果樹枝有分叉，一定是分 2 叉（就是說沒有只有 1 個(gè)兒子的結(jié)點(diǎn)）

這棵樹共有 N 個(gè)結(jié)點(diǎn)（葉子點(diǎn)或者樹枝分叉點(diǎn)），編號為 1 - N 樹根編號一定是 1。

我們用一根樹枝兩端連接的結(jié)點(diǎn)的編號來描述一根樹枝的位置。下面是一棵有 4 個(gè)樹枝的樹

2 5\ / 3 4\ /1

現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。

給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。

輸入

輸入包含多組測試數(shù)據(jù)。

對于每一組測試樣例：

第 1 行有 2 個(gè)數(shù)，N 和 Q(1 <= Q <= N，1 < N <= 100)。

N 表示樹的結(jié)點(diǎn)數(shù)，Q 表示要保留的樹枝數(shù)量。接下來 N-1 行描述樹枝的信息。

每行 3 個(gè)整數(shù)，前兩個(gè)是它連接的結(jié)點(diǎn)的編號。第 3 個(gè)數(shù)是這根樹枝上蘋果的數(shù)量。

每根樹枝上的蘋果不超過 30000 個(gè)。

輸出

一個(gè)數(shù)，最多能留住的蘋果的數(shù)量。

樣例輸入

5 2 1 3 1 1 4 10 2 3 20 3 5 20

樣例輸出

21

分析：

狀態(tài)表示：dp[i][j]表示子樹i，保留j個(gè)節(jié)點(diǎn)的最大權(quán)值
每條邊的權(quán)值，可以看作是兒子的權(quán)值，那么就可以對所有的子樹做分組背包，即每個(gè)子樹可以選則1,2..j-1條邊分配給它

#include<bits/stdc++.h> using namespace std; const int maxn=150; int dp[maxn][maxn]; vector< pair<int,int> >adj[maxn];//存儲無向圖 #define inf 0x3f3f3f3f int tot[maxn];//tot[i]表示與節(jié)點(diǎn)i直接相鄰的節(jié)點(diǎn)個(gè)數(shù) int dfs(int u,int fa)//u的父節(jié)點(diǎn)為fa {tot[u]=1;for(int i=0;i<adj[u].size();i++){int v=adj[u][i].first;if(v==fa) continue;tot[u]+=dfs(v,u);}for(int i=0;i<adj[u].size();i++){int v=adj[u][i].first;//與u直接相連節(jié)點(diǎn)int w=adj[u][i].second;//這條邊的權(quán)值if(v==fa) continue;for(int j=tot[u];j>1;j--){for(int k=1;(k<j)&&(k<=tot[v]);k++){dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]+w);}}}return tot[u]; } int main() {int n,p;while(~scanf("%d%d",&n,&p)){for(int i=0;i<maxn;i++)adj[i].clear();int u,v,w;for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&w);adj[u].push_back(make_pair(v,w));adj[v].push_back(make_pair(u,w));}memset(dp,0,sizeof(dp));dfs(1,-1);//從任意一點(diǎn)開始搜索printf("%d\n",dp[1][p+1]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的洛谷2015 二叉苹果树 树形DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。