给别人做金融网站 犯法吗,料远若近网站建设,点的排版设计网站,广告设计实习报告P2015 二叉苹果树 时间限制 1.00s 内存限制 125.00MB 题目描述 有一棵苹果树#xff0c;如果树枝有分叉#xff0c;一定是分2叉#xff08;就是说没有只有1个儿子的结点#xff09;
这棵树共有N个结点#xff08;叶子点或者树枝分叉点#xff09;#xff0c;编号为1-N,…P2015 二叉苹果树 时间限制 1.00s 内存限制 125.00MB 题目描述 有一棵苹果树如果树枝有分叉一定是分2叉就是说没有只有1个儿子的结点
这棵树共有N个结点叶子点或者树枝分叉点编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量求出最多能留住多少苹果。
输入格式 第1行2个数N和Q(1Q N,1N100)。
N表示树的结点数Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
每行3个整数前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
输出格式 一个数最多能留住的苹果的数量。
输入输出样例 输入 #1 复制 5 2 1 3 1 1 4 10 2 3 20 3 5 20 输出 #1 复制 21
解题思路 dp[u][j]dp[u][j]dp[u][j]以第uuu节点为根的子树保留jjj所留下的最大苹果数 则dp[u][j]max(dp[u][j],dp[u][j−k]dp[v][k−1]val)dp[u][j]max(dp[u][j],dp[u][j-k]dp[v][k-1]val)dp[u][j]max(dp[u][j],dp[u][j−k]dp[v][k−1]val) 因此要先一个循环遍历jjj的值jjj最多的值为树的边数与需保留的边数的较小值 还需遍历kkk的值即其子树能保留的边数
代码
#include cstdio
#include iostream
#include algorithm
#include cmath
#include cstdlib
#include cstring
#include map
#include stack
#include queue
#include vector
#include bitset
#include set
#include utility
#include sstream
#include iomanip
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e97;
struct node
{int to;int val;node(int _to,int _val) {to_to;val_val;}
};
vectornode m[120];
int n,k;
int dp[120][120];
int dfs(int s,int f) {int d0;for(int i0;im[s].size();i) {if(m[s][i].tof) continue;ddfs(m[s][i].to,s)1;for(int jmin(k,d);j0;j--) {for(int tmin(j,d);t0;t--) {dp[s][j]max(dp[s][j],dp[m[s][i].to][t-1]dp[s][j-t]m[s][i].val);}}}return d;
}
int main()
{#ifndef ONLINE_JUDGEfreopen(in.txt, r, stdin);#endif//freopen(out.txt, w, stdout);//ios::sync_with_stdio(0),cin.tie(0);scanf(%d %d,n,k);int a,b,c;rep(i,1,n-1) {scanf(%d %d %d,a,b,c);m[a].push_back(node(b,c));m[b].push_back(node(a,c));}dfs(1,0);printf(%d\n,dp[1][k]);return 0;
}
