注册登录

Pku2054 Color a Tree

本人水平有限，题解不到为处，请多多谅解

本蒟蒻谢谢大家观看

题目：传送门

翻译如下

　　　　　　　　　　问题A：Pku2054给树上色

描述

现在要对这N个结点依次进行
染色，每个结点染色要花费1个单位的时候，同时要满足一个结点仅在其
父亲被染色后才可被染色，每个结点有个权值Ci，如果我们在第Ti时间对
i号结点染色，则付出总代价为Sigma（Ti * Ci），1 <= i <= N。
现在认为这个树和每个点的权值，请构造一种染色顺序，使总代价最小。

输入项

输入包含几个测试用例。每种情况的第一行均包含两个整数N和R（1 <= N <= 1000，1 <= R <= N），其中N是树中的节点数，R是根节点的节点数。第二行包含N个整数，其中第i个为Ci（1 <= Ci <= 500），即节点i的着色成本因子。接下来的N-1行中的每一行都包含两个以空格分隔的节点号V1和V2，它们是树中边缘的端点，表示V1是V2的父节点。没有边缘将被列出两次，并且所有边缘将被列出。N = 0和R = 0的测试用例表示输入结束，不应进行处理。

输出量

对于每个测试用例，输出一行，其中包含Bob着色所有节点所需的最低总着色成本。

样本输入

5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0
知识兔

样本输出

33
知识兔

暗示

本题是一道合并类贪心，我们首先通过样例分析可知，一定要先染色完数值大的点，显然要贪心。

我们可以把大点向其父亲节点传递

不断找单位时间内值最大的点，即val[i]/tim[i]要最大

统计ans时，用当前点的值乘*其父亲节点的时间(时间已经累加到父亲节点上)

累加完当前节点的val之后记得要清零，防止重复累加

 我们要首先把所有点都染色一次，因为我们初始时间为1，在后面的统计中时间不会为1，所以其之前为时间1的值没有累加

code:

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 const int N=1e5+10;
 4 using namespace std;
 5 int n,R,ans;
 6 int fa[N],val[N];
 7 double tim[N];
 8 inline int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
11     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
12     return x*f;
13 }
14 inline void write(int x){
15      char F[200];
16      int tmp=x>0?x:-x ;
17      if(x<0)putchar('-') ;
18      int cnt=0 ;
19         while(tmp>0)
20         {
21             F[cnt++]=tmp%10+'0';
22             tmp/=10;
23         }
24         while(cnt>0)putchar(F[--cnt]) ;
25 }
26 int main()
27 {
28     while(n=read(),R=read()){
29         ans=0;
30         memset(fa,0,sizeof fa);
31         memset(tim,0,sizeof tim);
32         memset(val,0,sizeof val);
33         if(n==0&&R==0)return 0;
34         for(int i=1;i<=n;i++){
35             val[i]=read();
36             ans+=val[i];
37             tim[i]=1;
38         }
39         for(int i=1;i<n;i++){
40             int a,b;
41             a=read(),b=read();
42             fa[b]=a;
43         }
44         for(int i=1;i<n;i++){
45             double sum=0;
46             int id;
47             for(int i=1;i<=n;i++){
48                 if((double(val[i]/tim[i]>sum))&&(i!=R)){
49                     sum=(double)val[i]/tim[i];
50                     id=i;
51                 }
52             }
53             for(int i=1;i<=n;i++){
54                 if(fa[i]==id){
55                     fa[i]=fa[id];
56                 }
57             }
58             ans+=tim[fa[id]]*val[id];
59             tim[fa[id]]+=tim[id];
60             val[fa[id]]+=val[id];
61             val[id]=0;
62         }
63         printf("%d\n",ans);
64     }
65     return 0;
66 }
知识兔

注意：因为有多组数据，所以要初始化为0，存时间的数组类型要有double ,防止舍去了小数位，导致与标准数据相差1。

计算机