poj2054 Color a Tree
发布日期:2021-09-06 22:32:37 浏览次数:3 分类:技术文章

本文共 2280 字,大约阅读时间需要 7 分钟。

神题。这题是巨毒瘤...

自己写真可谓是:

排空驭气奔如电,上天入地求之遍

上穷碧落下黄泉,两处茫茫皆不见

由于我们知道:不是树形时,不停选值最大的节点可以得到最小代价。

那么我们就能想出一个错误的贪心:每次从能选的中选出最大的。

下面我们来构造反例:

 


 

      root

   ↙     ↘

 1         2

100

 


 

贪心:2 + 2 + 300 = 304

实际:1 + 200 + 6 = 207

那么我们该如何处理呢?

完全搞不倒啊!看题解看题解

得出如下结论:最大的节点一定是紧随着父节点染色的。

下一步:没有下一步....?????

我们要把这两个节点合并!

等效权值为平均数!

很遗恨的是,我只会证明两个点时权值是平均数。更多的还有待考证...

不过做题就是要靠想象!这就是正确的!

所以我们在代码实现的难题上继续败北......

我的想法是每个节点记录所有子节点以及所有合并过来的节点的顺序。用两个vector来实现。

然后那个堆是最困扰我的地方,实现起来困难重重。

看一看标程:cnm!直接n²暴力!

1000 * 1000 ......我觉得还行

然后我还发现了一件事:它没有记录次序!合并的同时更新ans!

惊为天人!

代码要简洁高效。这一点在寒假时我就有体会,现在又有这种感觉。

1 /** 2 poj 2054 3 */ 4 #include 
5 using namespace std; 6 typedef long long LL; 7 const int N = 1010; 8 const double eps = 1e-10; 9 10 struct Node {11 int tot, n, fa;12 bool del;13 double val;14 }node[N];15 16 int n, R;17 18 inline int find() {19 double maxval = -1;20 int ans = 0;21 for(int i = 1; i <= n; i++) {22 if(!node[i].del && i != R && node[i].val - maxval > eps) {23 maxval = node[i].val;24 ans = i;25 }26 }27 return ans;28 }29 30 inline int getfa(int k) {31 while(node[k].del) {32 k = node[k].fa;33 }34 return k;35 }36 37 int main() {38 scanf("%d%d", &n, &R);39 while(n || R) {40 LL ans = 0;41 node[R].fa = 0;42 for(int i = 1; i <= n; i++) {43 scanf("%d", &node[i].tot);44 node[i].val = (double)node[i].tot;45 node[i].n = 1;46 node[i].del = 0;47 ans += node[i].tot;48 }49 for(int i = 1; i < n; i++) {50 int x, y;51 scanf("%d%d", &x, &y);52 node[y].fa = x;53 }54 //printf("\n");55 for(int i = 1; i < n; i++) {56 int s = find();57 int f = getfa(node[s].fa);58 //printf("%d %d\n", s, f);59 ans += node[f].n * node[s].tot;60 node[f].n += node[s].n;61 node[f].tot += node[s].tot;62 node[f].val = (double)(node[f].tot) / node[f].n;63 //printf("%f\n", node[f].val);64 node[s].del = 1;65 }66 printf("%I64d\n", ans);67 scanf("%d%d", &n, &R);68 }69 return 0;70 }
AC代码

 

转载于:https://www.cnblogs.com/huyufeifei/p/9029150.html

转载地址:https://blog.csdn.net/weixin_34273481/article/details/93321666 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:第一次碰到try-except(core python programming 2nd Edition 3.6)
下一篇:[硬件]_ELVE_STLINK下载出现nternal command error问题

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月05日 11时57分33秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 2019-04-21
python类属性初始化_Python类定义、属性、初始化和析构 2019-04-21
mysql构建url给scrapy_Python Scrapy从mysq填充起始url 2019-04-21
owdcloud mysql_MySQL在Ubuntu远程配置 2019-04-21
python基础装饰器_Python基础 装饰器及练习 2019-04-21
python导出csv不带引号的句子_不带双引号写入CSV文件 2019-04-21
python爬虫代码模板_Python:学习Python爬虫的第一天 2019-04-21
springboot获取原生js请求_springboot跳转原生html 2019-04-21
java buffer nio_Java NIO之Buffer(缓冲区)入门 2019-04-21
android java加密_android 和java平台通用的AES加密解密 2019-04-21
java导出类_java导出excel工具类 2019-04-21
java学习手册下载_Java学习手册 2019-04-21
axios delete有请求体吗_关于axios请求——delete方法 2019-04-21
java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21
php继承exten,stylus中文文档 » 继承(@extend) » 张鑫旭-鑫空间-鑫生活 2019-04-21