$Poj2054\ Color\ a\ Tree\ $ 贪心

2022-10-28 15:04:01

$poj$

$Description$

一颗树有 $n$ 个节点,这些节点被标号为:$1,2,3…n,$每个节点 $i$ 都有一个权值 $A[i]$。

现在要把这棵树的节点全部染色,染色的规则是:

根节点R可以随时被染色;对于其他节点,在被染色之前它的父亲节点必须已经染上了色.

每次染色的代价为$T*A[i]$,其中$T$代表当前是第几次染色.

求把这棵树染色的最小总代价。

$Sol$

贪心:树中权值最大的点,一定会在它的父结点染色后立即染色

可以这样想,假设没有树的约束,只是一个序列,那么显然是按照从大到小排序的顺序染色为最优,现在有树的约束条件,也应该让权值最大的尽量早地染色.

因为权值最大的点与它的父结点的染色是接连进行的,所以我们可以把它们合并起来.

现在有权值为$x,y,z$的三个点,已知$x$和$y$的染色是接连着进行的,其中$x$是$y$的父结点.那么有两种决策.

1.先染$x,y$,再染$z$ ,$x+2y+3z=y+(x+y)+3z$

2.先染$z$,再染$x,y, z+2x+3y=z+y+2*(x+y)$

发现无论是上面的哪种情况有一种做法是通用的:先把$y$累加进答案,然后把$y$结点与$x$结点合并,具体来说,$x$的权值改为$(x+y)/2$,删除$y$结点.为什么是把权值改成$(x+y)/2$呢?

有一个十分重要的问题,就是如何判断这两种做法的优劣.设合并后的结点为$i$,这个结点所包含的结点数(它自己和合并进去的)为$s[i]$,包含的所有的权值和为$a[i]$.

1.$a[i]+(s[i]+1)*z.$

2.$z+a[i]*2.$

发现应该把$1$式中的$z$的系数变成$2$,把两个式子同时加上$(s[i]-1)*z$,再同除$s[i]$,变成

1.$a[i]/s[i]+2*z$

2.$z+a[i]/s[i]$

可以看成权值为$a[i]/s[i]$的结点和$z$的两个结点,根据最开始所说的贪心可知比较它们的大小就能决定先给谁染色了,于是问题就解决了.

还是要强调的是上面所赋予的新权值只能用于与别的结点比较大小从而决定染色顺序,至于答案的累加,就在对于最初始的两个式子的分析中"把$y$累加进答案"这句话.具体来说$j$结点累加进$i$结点,$ans+=a[j]*s[i]$.

$Code$

#include<iostream>

#include<cstdio>

#define il inline

#define Rg register

#define go(i,a,b) for(Rg int i=a;i<=b;i++)

#define yes(i,a,b) for(Rg int i=a;i>=b;i++)

#define db double

#define ll long long

using namespace std;

il int read()

{

    int x=,y=;char c=getchar();

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

    return x*y;

}

int n,rt,a[],fa[],s[];

ll as;

int main()

{

    //while(1)

    {

        n=read(),rt=read();as=;

        if(!n && !rt)return ;

        go(i,,n)a[i]=read(),s[i]=;

        go(i,,n-){int x=read(),y=read();fa[y]=x;}

        go(T,,n-)

        {

            db maxs=;int pos;

            go(i,,n)

                if(i!=rt && 1.0*a[i]/s[i]>=maxs)maxs=1.0*a[i]/s[i],pos=i;

            go(i,,n)

                if(fa[i]==pos)fa[i]=fa[pos];

            as+=a[pos]*s[fa[pos]];

            s[fa[pos]]+=s[pos];

            a[fa[pos]]+=a[pos];

            a[pos]=;

        }

        as+=a[rt];

        printf("%lld\n",as);

    }

    return ;

}

随机推荐

mac版微信web开发者工具（小程序开发工具）无法显示二维码解决方案
微信小程序概念的提出,绝对可以算得上中国IT界惊天动地的一件大事,这可能意味着一场新的开发热潮即将到来, 我也怀着激动的心情准备全身心投入其中,不过截止目前,在官方网站上下载的最新版本都无法使用,打开 ...
linux性能监控工具
1.uptime 该命令直观的显示了服务器在过去15分钟,5分钟,1分钟内的平均负载 2.vmstat 每隔2秒输出vmstat的信息,共输出10次. 类别 procs swap io sys ...
Jni 类型转换接口
1.JString char*互相转化 char* JstringToChar(JNIEnv* env, jstring jstr) { char* rtn = NULL; jclass clsstr ...
全国各城市Uber客服联系方式（电话、邮箱、微博）
滴快车单单2.5倍,注册地址:http://www.udache.com/ 如何注册Uber司机(全国版最新最详细注册流程)/月入2万/不用抢单:http://www.cnblogs.com/mfry ...
LINUX下使用crontab进行RMAN备份实验
之前写了脚本,手动执行可以,使用crontab总是无法运行成功,今天下午花了两个小时实验,完成如下: 注意事项:脚本完成首先手动执行,确定可以正常执行. 在crontab中使用,要注意以下几点: 1. ...
ABAP 数值四舍五入函数
VALUE '12.5445' , dat1 . VALUE '12.540'. * 方法一 CALL FUNCTION 'HR_NZ_ROUNDING_DECIMALS' EXPORTING val ...
Ubuntu 16&period;04 安装Google 浏览器
Ubuntu安装好后,自带Firefox浏览器,有时我们需要再安装几个浏览器,那么Google Chrome,就是首选, 安装如下: 下载浏览器安装包, 下载链接:https://dl.google. ...
springboot swagger2 泛型踩坑记
最近使用一些工具需要和swagger打通,swagger的格式总是不对. 后来查了一下:哈哈. https://blog.csdn.net/hupingjin/article/details/8299 ...
flink的Standalone集群安装
1:上传安装包到linux系统使用rz命令 2:解压 tar –zxvf flink-1.5.0-bin-hadoop24-scala_2.11.tgz 3:修改配置文件 vim conf/flin ...
Java工程师学习指南中级篇
Java工程师学习指南中级篇最近有很多小伙伴来问我,Java小白如何入门,如何安排学习路线,每一步应该怎么走比较好.原本我以为之前的几篇文章已经可以解决大家的问题了,其实不然,因为我写的文章都是站 ...

码农公寓

随机推荐

相关文章