Ural 1018 (树形DP+背包+优化)

60 阅读 0 评论 40 点赞

我是靠谱客的博主完美水杯，最近开发中收集的这篇文章主要介绍Ural 1018 (树形DP+背包+优化)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17662

题目大意：树枝上间连接着一坨坨苹果（不要在意'坨')，给定留下m根树枝，问最后剩下的最多苹果是多少。

解题思路：

其实意思和Vijos 1180（选课）的意思差不多。只不过权在边而已。

首先建无向图dfs。

for(f+1...j....cost)

for(1....k...j-cost)

其中f为当前已经dfs子结点个数。之所以+1，是因为当前点也需要分配一根树枝才能取到这个点的苹果。

f+=dfs(t)，dfs(t)返回的是子点t的f+1。

其实可以直接把f+1写成m+1, 不过要多好多次没必要的循环。

最后结果就是dp[1][m+1]，注意由于树结构，1上的苹果是默认都能取到，但是按照这种DP方式要取到1上苹果，还需要加一个虚枝才行，也就是为什么是m+1。

#include "cstdio"
#include "queue"
#include "iostream"
#include "cstring"
using namespace std;
#define maxn 105
int n,m,dp[maxn][maxn],head[maxn],tol;
struct Edge
{
int next,to,w;
}e[maxn*2];
void addedge(int u,int v,int w)
{
e[tol].to=v;
e[tol].next=head[u];
e[tol].w=w;
head[u]=tol++;
}
int dfs(int root,int pre)
{
int cost=1,i=root,f=0;
for(int a=head[root];a!=-1;a=e[a].next)
{
int t=e[a].to;
if(t==pre) continue;
f+=dfs(t,root);
for(int j=f+1;j>=1;j--)
for(int k=1;k<=j-cost;k++)
dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]+e[a].w);
}
return f+cost;
}
int main()
{
//freopen("in.txt","r",stdin);
int u,v,w;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
dfs(1,1);
printf("%dn",dp[1][m+1]);
}