题意：给出一个二叉树，每条边上有一定的边权，并且剪掉一些树枝，求留下 Q 条树枝的最大边权和。 （ 节点数 n ≤100，留下的枝条树 Q ≤ n ，所有边权和 ∑w[i] ≤30000 ）
细节：对于一棵子树 u 来说如果剪掉 u 节点上方的树枝，则该子树内的所有树枝都相当于被剪去。
分析：由于是二叉树，所以转移就与左右子树有关，其次我们需要求出最大的边权和，而且需要记录当前子树保留了多少枝条。
所以 Dp 的状态：dp[u][j] 表示以 u 为根保留了 j 条树枝（包括 u 的前一条树枝）
转移： dp[u][j] = max( dp[lx[u]][k] + dp[ly[u]][j-k-1] + Pre[u], dp[u][j] ) lx[u]表示 u 的左子树，ly[u]表示 u 的右子树，Pre[u]表示 u 的前一条边
（ j≤size[u]，k≤min( size[lx[u]] , j-1) ）size[u]表示以 u 为子树的节点个数
代码如下：
#include <bits/stdc++.h>
#define MAXN 105
using namespace std;
struct edge{
int to, Next, val;
}Right[MAXN<<1];
int Begin[MAXN], f[MAXN][MAXN], Pre[MAXN], size[MAXN], n, q, cnt, lx[MAXN], ly[MAXN];
inline void add_edge(int x, int y, int z){
Right[++cnt].to=y;
Right[cnt].Next=Begin[x];
Begin[x]=cnt;
Right[cnt].val=z;
}
void build(int u, int fa){
size[u]=1;
for (int i=Begin[u]; i; i=Right[i].Next){
int v=Right[i].to;
if (v==fa) continue;
Pre[v]=Right[i].val;
if (!lx[u]) lx[u]=v;
else ly[u]=v;
build(v, u);
size[u]+=size[v];
}
}
void solve(int u, int fa){
for (int i=Begin[u]; i; i=Right[i].Next){
int v=Right[i].to;
if (v==fa) continue;
solve(v, u);
for (int j=2; j<=size[u]; j++)
for (int k=0; k<=min(size[lx[u]], j-1); k++)
f[u][j]=max(f[u][j], f[lx[u]][k]+f[ly[u]][j-k-1]+Pre[u]);
}
}
int main(){
scanf("%d%d", &n, &q);
for (int i=1; i<n; i++){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add_edge(x, y, z);
add_edge(y, x, z);
}
build(1, 0);
for (int i=1; i<=n; i++) f[i][1]=Pre[i];
solve(1, 0);
printf("%dn", f[1][q+1]);
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
