G-rated

What are you waiting for?

0%

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;
}