题目
在一棵树上有n个节点(从0开始),在每个节点上都有一些苹果,现在需要在这棵树上把一些苹果从一个节点搬到另一个节点,使得这些节点上的苹果数的方差最小,从a节点搬运x个苹果到b节点的花费为x*dist(a,b),求满足条件的最小花费是多少?
思路
想了很久。。。
一开始发现,对于一个节点而言,其上最终的苹果数一定是平均数(取整后的)或是平均数+1,我们定义前者为情况1,后者为情况2,这样我们就可以把方差这一维消掉。
之后,我们跑一个分组背包。
$dp[i][j]$表示当前节点中,情况2的点的个数。
我们看得不是点的贡献,而是每条边的贡献(这也是在处理树上路径问题点权决策复杂的基本套路)。
接下来就是初值的问题,对于叶子节点而言,dp的值显然都是0(此子树内部的边不发生代价)。
那么对于非叶子节点来说呢?
我们无法简单地赋一个初值给它,因为这个节点的所有信息显然都是来自它的子孙的,但如果我们不赋初值,那么dp就没法更新。
所以,对于dp[x][0]和dp[x][1]我们分别表示,对于x自身,把它变成1情况和2情况的最小花费。而这是不需要花费的,所以,我们把这两个dp赋成0,本层就可以更新了。
但是,dp[x][0]和dp[x][1]表示的不仅仅是它自己的状态,也包含了子树中的解,所以我们不能把它当做最终的结果,它的存在,只是为了能让自己和其他的解进行更新,所以要先开一个tmp,最后再赋回去。
代码
#include<bits/stdc++.h>
#define M 105
#define LL long long
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
int h[M],tot;
struct edge{
int nxt,to,co;
}G[M*2];
void Add(int a,int b,int c){
G[++tot]=(edge){h[a],b,c};
h[a]=tot;
}
#define DEG(a,st) for(int a=h[st];a;a=G[a].nxt)
int A[M],sz[M],n,sum[M],res;
LL dp[M][M],S,pj;//在当前节点有几个是pj+1,其余的全是pj,的最小花费
void dfs(int x,int f){
sz[x]=1;sum[x]=A[x];
dp[x][0]=dp[x][1]=0;
DEG(i,x){
int u=G[i].to,v=G[i].co;
if(u==f)continue;
dfs(u,x);
sz[x]+=sz[u];sum[x]+=sum[u];
for(int j=res;j>=0;j--){
LL tmp=1e18;
for(int r=0;r<=min(sz[u],j);r++){
int dis=abs(r*(pj+1)+(sz[u]-r)*pj-sum[u])*v;
tmp=min(tmp,dp[x][j-r]+dp[u][r]+dis);
}
dp[x][j]=tmp;
}
}
}
int main(){
while(~scanf("%d",&n)){
clr(h,0);tot=0;S=0;
for(int i=0;i<n;i++)scanf("%d",&A[i]),S+=A[i];
pj=S/n;
res=S-pj*n;
for(int i=1,a,b,c;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
Add(a,b,c);
Add(b,a,c);
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)dp[i][j]=1e18;
dfs(0,-1);
cout<<dp[0][res]<<endl;
}
return 0;
}