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=200;
const int inf=2147483647; int n,Q;
vector<Edge> E[maxN];
bool vis[maxN];
int F[maxN][maxN]={0}; int dfs(int u); int main()
{
int u,v,w;
cin>>n>>Q;
for (int i=1;i<n;i++)
{
cin>>u>>v>>w;
E[u].push_back((Edge){v,w});
E[v].push_back((Edge){u,w});
}
memset(vis,0,sizeof(vis));
dfs(1);
cout<<F[1][Q]<<endl;
return 0;
} int dfs(int u)
{
int cnt=0;//统计子树枝个数
vis[u]=1;
for (int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if (vis[v]==0)
{
cnt+=dfs(v)+1;//每次要+1,即加上u->v这条边
for (int j=min(Q,cnt);j>=1;j--)//要取min的原因是要简化循环
for (int k=j;k>=1;k--)
{
F[u][j]=max(F[u][j],F[u][j-k]+F[v][k-1]+E[u][i].w);
}
}
}
return cnt;
}
上一篇:web安全测试工具的局限性


下一篇:How to use AKBusGpsParser