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; }

转载于:https://www.cnblogs.com/SYCstudio/p/7138194.html

相关资源：JAVA上百实例源码以及开源项目