zoj 3231 Apple Transportation

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp 背包

题意:无根树,每条边有边权,每个点有苹果数,你可以任意移动苹果,每一个苹果走过一条边的花费就是边权,如果同时m个苹果走过一条边的花费为m*w。为怎么移动,使得整个树,每个节点上的苹果的数量的方差最小,题目下面的Hint给出了方差的公式

题目一个突破点是抛弃方差公式,那个公式是多余的,起了迷惑作用。我们回到方差的定义,其实就是令到各个点的苹果数尽量相同,最好的结果就是平均分,这样方差为0,。另外是整数,所以不能整除的话,会有一些点的苹果数多1

设全部苹果数为sum,点数为n,ave=sum/n,即平均数
num = sum % n; 如果不能整除,就会有num个点多出1个苹果,即ave+1个苹果
分析到这一步,就可以背包了

也就说,最终树的样子就是,有num个点有ave+1个苹果,把这些点称为红点,有n-num个点有ave个苹果,称为黑点,问题变成了,通过运输把哪些点变为红点哪些点变为黑点会使花费最小?

dp[u][m]表示u的子树下,有m个红点的最小花费

要计算dp[u][m]要考虑u的所有儿子子树和u这个点本身,而u这个点本身是不是红点可以放在最后考虑,在转移的时候先考虑子树

这个背包,写起来不像是一般写的树dp背包,在转移的时候会出问题(主要是利用了滚动数组),我设置了一个LL res;方便转不出错。另外一开始只考虑子树,最后才考虑u这个点本身,所以一开始转移的时候利用一个临时数组tmp[]来代替,最后再把tmp[]的信息传递给dp
整个专题方程,有些许细节,主要是运输,要考虑运多少苹果,走过一条边的花费即代码中计算的cost,在此不多说了,看代码吧,转移确实有点难度,多看几次就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 110
#define INF 100000000000LL
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N],val[N],sum,ave,num;
int cnt[N],totval[N],up[N];
struct edge{
int u,v,w,next;
edge(){}
edge(int __u,int __v,int __w){
u = __u; v = __v; w = __w;
}
}e[2*N];
LL dp[N][N];

inline int Abs(int x){
return x > 0 ? x : -x;
}

inline void add(int u,int v,int w){
e[tot] = edge(u,v,w);
e[tot].next = head[u]; head[u] = tot++;
}

void updata(int u,int fa){
int cap = min(cnt[u],num);
LL tmp[N];
fill(tmp,tmp+n,INF); tmp[0] = 0;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
int w = e[k].w;
if(v == fa) continue;
for(int j = cap; j >= 0; j--){
LL res = INF;
//这个res的设置是关键,不能直接tmp[j] = min(tmp[j] , tmp[j-k] + dp[v][k]);
for(int k = 0; k <= j && k <= cnt[v]; k++)
if(tmp[j-k] != INF && dp[v][k] != INF)
res = min(res , tmp[j-k]+dp[v][k]);
tmp[j] = res;
}
}
for(int i = 0; i <= cap; i++){ //最后才考虑u这个点要不要取上整
LL cost = up[u] * Abs(ave * cnt[u] + i - totval[u]);
if(i == 0) dp[u][0] = tmp[0] + cost;
else dp[u][i] = min(tmp[i-1] , tmp[i]) + cost;
}
}

void dfs(int u,int fa,int weigth){
bool leaf = true;
cnt[u] = 1; up[u] = weigth;
totval[u] = val[u];
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
int w = e[k].w;
if(v == fa) continue;
leaf = false;
dfs(v,u,w);
cnt[u] += cnt[v];
totval[u] += totval[v];
}
if(leaf){
int cost;
cost = up[u] * Abs(ave*cnt[u]-totval[u]);
dp[u][0] = cost;
cost = up[u] * Abs(ave*cnt[u]+1-totval[u]);
dp[u][1] = cost;
return;
}
updata(u,fa);
}

int main(){
while(scanf("%d",&n)!=EOF){
tot = sum = 0; cl(head,-1);
for(int i = 0; i < n; i++){
scanf("%d",&val[i]);
sum += val[i];
}
for(int i = 1; i < n; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
ave = sum / n; num = sum % n;
fill(dp[0],dp[n],INF);
dfs(0,-1,0);
printf("%lld\n",dp[0][num]);
}
return 0;
}