ZOJ 3201

90 阅读 0 评论 60 点赞

我是靠谱客的博主丰富草丛，最近开发中收集的这篇文章主要介绍ZOJ 3201，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Tree of Tree

Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %lld & %llu

Description

You're given a tree with weights of each node, you need to find the maximum subtree of specified size of this tree.

Tree Definition
A tree is a connected graph which contains no cycles.

Input

There are several test cases in the input.

The first line of each case are two integers N(1 <= N <= 100), K(1 <= K <= N), where N is the number of nodes of this tree, and K is the subtree's size, followed by a line with N nonnegative integers, where the k-th integer indicates the weight of k-th node. The following N - 1 lines describe the tree, each line are two integers which means there is an edge between these two nodes. All indices above are zero-base and it is guaranteed that the description of the tree is correct.

Output

One line with a single integer for each case, which is the total weights of the maximum subtree.

Sample Input

Sample Output

30
40

Source

ZOJ Monthly, May 2009

树状DP~

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 105
int n,k,dp[maxn][maxn],val[maxn];
vector <int> edge[maxn];
void dfs(int u,int y)
{
dp[u][1] = val[u];
for(int i = 0;i < edge[u].size();i ++)
{
int v = edge[u][i];
if(v == y) continue;
dfs(v, u);
for(int j = k;j > 0;j --)
//类似01背包
for(int p = 0;p < j;p ++)
{
dp[u][j] = max(dp[u][j], dp[u][j-p] + dp[v][p]);
}
}
}
int main()
{
int a, b,ans;
while(scanf("%d%d", &n, &k) != EOF)
{
ans = -1;
memset(dp, -1, sizeof(dp));
for(int i = 0;i < n;i ++)
edge[i].clear();
for(int i = 0;i < n;i ++)
scanf("%d", &val[i]);
for(int i = 0;i < n-1;i ++)
{
scanf("%d%d",&a,&b);
edge[a].push_back(b);
edge[b].push_back(a);
}
dfs(0, -1);
for(int i = 0;i < n;i ++)
ans = max(ans, dp[i][k]);
printf("%dn", ans);
}
return 0;
}