当前位置:网站首页>Luo Gu p3177 tree coloring [deeply understand the cycle sequence of knapsack on tree]
Luo Gu p3177 tree coloring [deeply understand the cycle sequence of knapsack on tree]
2022-07-05 08:52:00 【Qizi K】
Pre knowledge :
AcWing 10 Backpack on the tree —— There is a knapsack problem of dependence
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m,root,dp[N][N];
int idx, ne[N], e[N], h[N], w[N], v[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
void dfs(int u){
for(int i = h[u]; ~i; i = ne[i]){
int son = e[i];
dfs(son);
for(int j = m - v[u]; j; j --)
for(int k = 0; k <= j; ++ k)
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
}
for(int i = m; i >= v[u]; -- i) dp[u][i] = dp[u][i - v[u]] + w[u];
for(int i = 0; i < v[u]; ++ i) dp[u][i] = 0;
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; ++ i){
int p;
cin >> v[i] >> w[i] >> p;
if(p == -1) root = i;
else add(p, i);
}
dfs(root);
cout << dp[root][m];
return 0;
}
This topic tips: Deform the statistical answer in the question , Become statistics The sum of the edge weight of each edge multiplied by the number of black dots on both sides and the edge weight multiplied by the number of white dots on both sides 【 It can be understood as : Each pair of nodes with different colors on both sides of this edge , The statistical answer will pass this side once . So the total number of passes is the product of the number of black spots on both sides + The product of white dots on both sides 】, It turns into the knapsack problem on the tree .
About the problem of cycle order :
1、 For the first layer of circulation j From big to small , Because the grouping backpack is omitted “ grouping ” One dimension of , So we can only flashback enumeration , This is the knapsack problem ;
2、 For the second layer, enumerate the number of black dots in the subtree k, It looks like Must enumerate in positive order . In an ordinary tree backpack , The order of enumeration at this level does not matter , because k = 0 Say no , It won't affect the answer ; There are no black spots in the operator tree , White dots will still affect the answer , therefore k = 0 It should be calculated first , So we need to The reason for positive enumeration is positive enumeration k It's from 0 At the beginning , And the state transition of this problem must first be k=0 Can be established only when the state of is transferred .
A better understanding explanation :
“ But this problem is quite special , It's ours k Can be equal to 0, This leads to a lack of confidence For every j, the last one k There must be an illegal transfer . Popular point , The last transfer is :f[u][j]=max(f[u][j],f[u][j]+f[v][0]+val); This shift is bound to happen , And the source state we use f[u][j-k] because k=0 Of reason , It has not met our original requirements “ The original state we need will not be here Update before ” 了 , because f[u][j] I don't know how many times it has been updated .”
So if you deal with it first k = 0 The situation of , In fact, it doesn't matter to enumerate in reverse order .
About why this problem needs to be initialized before making a tree knapsack -1 The problem of :—— Remove illegal situations :
We enumerate in the subtree of the current child node , Let's enumerate it. There are k A black spot , Then we need one that selects a total of j - k The state of a black dot , however If the total size of other subtrees is less than j - k Words , Then this state is obviously illegal , So we need to get rid of this situation .
General tree backpack , There is no such thing , Because the maximum volume is m, All that is missing must be used , So there is no need to remove illegal situations .
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4010;
int idx, ne[N], e[N], h[N];
int n,k1,sz[N];
ll dp[N][N], w[N];
void add(int a, int b, ll c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}
void dfs(int u, int fa){
sz[u] = 1;
dp[u][0] = dp[u][1] = 0;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa) continue;
dfs(j, u);
sz[u] += sz[j];
}
for(int i = h[u]; ~i; i = ne[i]){
int son = e[i];
if(son == fa) continue;
for(int j = min(sz[u], k1); j >= 0; j --){
for(int k = 0; k <= min(j, sz[son]); ++ k){
if(dp[u][j - k] >= 0){
ll val = (ll)k * (k1 - k) * w[i] + (ll)(sz[son] - k) * (n - k1 - sz[son] + k) * w[i];
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k] + val);
}
}
}
}
}
int main(){
cin >> n >> k1;
memset(h, -1, sizeof h);
memset(dp, -1, sizeof dp);
for(int i = 1; i < n; ++ i){
int a, b; ll c;
scanf("%d%d%lld",&a,&b,&c);
add(a,b,c), add(b,a,c);
}
dfs(1,1);
cout << dp[1][k1];
return 0;
}
边栏推荐
猜你喜欢
[牛客网刷题 Day4] JZ55 二叉树的深度
Programming implementation of ROS learning 5-client node
Count of C # LINQ source code analysis
Confusing basic concepts member variables local variables global variables
Digital analog 1: linear programming
Codeworks round 639 (Div. 2) cute new problem solution
Guess riddles (142)
Halcon clolor_ pieces. Hedv: classifier_ Color recognition
[matlab] matlab reads and writes Excel
Run菜单解析
随机推荐
One dimensional vector transpose point multiplication np dot
asp. Net (c)
12、动态链接库,dll
Yolov4 target detection backbone
Use arm neon operation to improve memory copy speed
Guess riddles (142)
Run菜单解析
golang 基础 ——map、数组、切片 存放不同类型的数据
Halcon Chinese character recognition
File server migration scheme of a company
【日常训练--腾讯精选50】557. 反转字符串中的单词 III
特征工程
[Niuke brush questions day4] jz55 depth of binary tree
It cold knowledge (updating ing~)
Halcon: check of blob analysis_ Blister capsule detection
MPSoC QSPI flash upgrade method
Blue Bridge Cup provincial match simulation question 9 (MST)
[牛客网刷题 Day4] JZ55 二叉树的深度
多元线性回归(sklearn法)
Typescript hands-on tutorial, easy to understand