【题目描述】
有一棵二叉苹果树,如果数字有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵树共
N 个节点,标号1 至 N ,树根编号一定为 1 。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树,因为树枝太多了,需要剪枝。但是一些树枝上长有苹果,给定需要保留的树枝数量,求最多能留住多少苹果。
【输入】
第一行两个数 N 和 Q ,N 表示树的节点数,Q 表示要保留的树枝数量。
接下来N−1行描述树枝信息,每行三个整数,前两个是它连接的节点的编号,第三个数是这根树枝上苹果数量。
【输出】
输出仅一行,表示最多能留住的苹果的数量。
【输入样例】
5 2
1 3 1
1 4 10
2 3 20
3 5 20
【输出样例】
21
【提示】
数据范围与提示:
对于 100 的数据,1≤Q≤N≤100,N≠1 ,每根树枝上苹果不超过 30000 个。
#include<bits/stdc++.h>
using namespace std;
int lson[105], rson[105], w[105];
int mat[105][105];
int n, q;
void dfs(int u) {
for (int i = 1; i <= n; i++) {
if (mat[u][i] >= 0) {
lson[u] = i;
w[i] = mat[u][i];
mat[u][i] = mat[i][u] = -1;
dfs(i);
break;
}
}
for (int i = 1; i <= n; i++) {
if (mat[u][i] >= 0) {
rson[u] = i;
w[i] = mat[u][i];
mat[u][i] = mat[i][u] = -1;
dfs(i);
break;
}
}
}
int dp[105][105];
int solve(int u, int x) {
if (x == 0)return 0;
if (u == 0) return -1e9;
if(dp[u][x]!=-1)return dp[u][x];
int res = -1e9;
for (int i = 0; i < x; i++)
res = max(res, solve(lson[u], i) + solve(rson[u], x - 1 - i) + w[u]);
return dp[u][x]=res;
}
int main() {
cin >> n >> q;
memset(mat, -1, sizeof(mat));
memset(dp,-1,sizeof(dp));
for (int i = 1; i <= n; i++) {
int x, y, w;
cin >> x >> y >> w;
mat[x][y] = mat[y][x] = w;
}
dfs(1);
cout << solve(1, q + 1);
return 0;
}
标签:return,mat,int,树枝,C++,二叉,苹果树,dp,105 From: https://blog.csdn.net/qxh10/article/details/140418293