HDU 1055

题目大意：给你一棵树，数有N个节点，每个节点有权重w。你需要给这棵树的每一个节点进行涂色，每涂一个节点花费一个单位时间，开始时间设定为0，对于一个权重为W的节点，假定你在第T个的单位时间完成对它的涂色，那么对它的涂色的代价C=W*T，同时规定只有当某个节点父节点已经完成涂色时，你才能对它进行涂色操纵。要求你求出完成整颗树的涂色所需要的最小的花费。

题解：这是道贪心的题目。首先我们看代价计算公式：C=T*W，我们很容易想到权重越大的节点我们应该尽早涂色，但限于规定--只有当某个节点父节点已经完成涂色时，你才能对它进行涂色，所以我们这样简易的想法显然是行不通的。虽然当前权重最大的节点我们不一定可以马上进行涂色，但不难想到，该节点的涂色一定是紧接着它的父亲节点的。于是，假设当前权重最大的节点为k，它的父亲节点为p，我们可以将这两个节点合并成一个新节点p'，p'的父亲节点为p的父亲节点，p'的子节点为p以及k的子节点，我们对p'节点涂色所需时间p’.t=p.t+k.t，节点p'的总权重p'.c=p.c+k.c，节点p的平均权重p'.w=p'.c/p'.t。对于新节点p'涂色花费时间的更新我觉得很好理解，至于对p'.c的更新我是这么理解的，节点p'每晚一个单位时间进行涂色，对p'进行涂色所需要花费的代价就要增加p'.c。对于p'的平均权重p'.w，它具有很重要的比较意义，我们是通过它来判断当前该被合并的节点是哪个。那为什么会有p'.w=p'.c/p'.t呢？假设现在有两个节点A，B，当我们把节点A放在节点B前面进行涂色时，节点B进行涂色增加的代价为ExCost_B=B.c*A.t，当我们把节点B放在节点A前面进行涂色时，节点A进行涂色增加的代价为ExCost_A=A.c*B.t，同时无论节点A或B谁在前面，整个过程的基础代价（一定会花费的代价）都一样。于是通过比较ExCost_A和ExCost_B就可以得知那个方案更优，当有ExCost_A>ExCost_B ==> A.c*B.t>B.c*A.t ==> A.c/A.t>B.c/B.t ==> A.w>B.w，也就是当A的平均权重大于B的时，应该把节点A放在节点B的前面（即对节点A先进行涂色）。

代码如下：

#include<cstdio>#include<cstring>#include<iostream>#include<vector>#include<algorithm>using namespace std;int n,r,ans;struct node{    int PRe,c,t;    double w;}e[1505];int main(){    while(scanf("%d%d",&n,&r),n+r){        int u,v;        ans=0;        for(int i=1;i<=n;++i){            scanf("%d",&e[i].c);            e[i].t=1;            e[i].w=e[i].c;            ans+=e[i].c;        }        for(int i=1;i<n;++i){            scanf("%d%d",&u,&v);            e[v].pre=u;        }        for(int i=1;i<n;++i){            double maxn=-1;            int k;            for(int i=1;i<=n;++i){                if(i==r) continue;                if(e[i].w>maxn){                    maxn=e[i].w;                    k=i;                }            }            int p=e[k].pre;            ans+=e[k].c*e[p].t;            e[k].w=0;            for(int i=1;i<=n;++i)                if(e[i].pre==k)                e[i].pre=p;            e[p].c+=e[k].c;            e[p].t+=e[k].t;            e[p].w=e[p].c*1.0/e[p].t;        }        printf("%d/n",ans);    }    return 0;}