本文出自 http://blog.csdn.net/shuangde800
---------------------------------------------------------------------------------
題目連結: url-1018
題意
給一棵邊有權值的二叉樹,節點編号為1~n,1是根節點。求砍掉一些邊,隻保留q條邊,這q條邊構成的子樹
的根節點要求是1,問這顆子樹的最大權值是多少?
思路
非常經典的一道樹形dp題,根據我目前做過的題來看,有多道都是由這題衍生出來的。
f(i, j) 表示子樹i,保留j個節點(注意是節點)的最大權值。每條邊的權值,把它看作是連接配接的兩個節點中的兒子節點的權值。
那麼,就可以對所有i的子樹做分組背包,即每個子樹可以選擇1,2,...j-1條邊配置設定給它。
狀态轉移為:
f(i, j) = max{ max{f(i, j-k) + f(v, k) | 1<=k<j} | v是i的兒子}
ans = f(1, q+1)
代碼
/**=====================================================
* This is a solution for ACM/ICPC problem
*
* @source : ural-1018 Binary Apple Tree
* @description : 樹形dp
* @author : shuangde
* @blog : blog.csdn.net/shuangde800
* @email : [email protected]
* Copyright (C) 2013/09/01 18:43 All rights reserved.
*======================================================*/
#include
#include
#include
#include
#include
#define MP make_pair using namespace std; typedef pair
PII; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 110; vector
adj[MAXN]; int n, q; int tot[MAXN]; int f[MAXN][MAXN]; int dfs(int u, int fa) { tot[u] = 1; for (int e = 0; e < adj[u].size(); ++e) { int v = adj[u][e].first; if (v == fa) continue; tot[u] += dfs(v, u); } for (int e = 0; e < adj[u].size(); ++e) { int v = adj[u][e].first; int w = adj[u][e].second; if (v == fa) continue; for (int i = tot[u]; i > 0; --i) { for (int j = 1; j < i && j <= tot[v]; ++j) { f[u][i] = max(f[u][i], f[u][i-j] + f[v][j] + w); } } } return tot[u]; } int main(){ while (~scanf("%d%d", &n, &q)) { for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 0; i < n - 1; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back(MP(v, w)); adj[v].push_back(MP(u, w)); } memset(f, 0, sizeof(f)); dfs(1, -1); printf("%d\n", f[1][q+1]); } return 0; }