RainAir
My OI Blog
RainAir
最小树形图 / 朱刘算法

前置定义

树形图:在一个有向图中,满足存在一个入度为 $0$ 的点,除了该点入读均为 $1$,且该图不存在环,那么称为树形图。
最小树形图:给定有向边权图,求以某点为根的边权和最小的子图,满足该子图为树形图。

朱刘算法

模板链接
相当于是一种贪心的思想。
首先我们发现一个合法的树形图中除根外的每个点只有一条入边,所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环,所以我们可以暴力把这些环缩起来然后在新图中跑上述过程一直到找不到环为止。
但是注意到我们每此跑了一遍算法后,答案已经加上每个点的最短入边了,为了防止重复计算答案,要把其他的边长减去原来的最短入边边长,然后继续计算。
代码:

实际运用

接下来我们看一道例题:题目链接
(权限题,若查看不了请点击
首先发现我们对于所有要买的东西,只需要第一次都买过一边后,剩下的都用优惠价格购买就可以了。
所以第一次以后的购买总额我们可以计算出来了,关键是确定所有物品第一次的购买顺序。
我们对于每一个物品都看作一个节点,考虑建立一个虚拟节点 $S$ ,连向所有物品一条长度为该物品第一次购买的价格;如果 $u$ 购买后能给予 $v$ 优惠,那么我们就从 $u$ 向 $v$ 连长度为优惠后的价格的边。
考虑这张图的最小树形图的意义:所有的点都被选择且选择总代价最小。
那么这个题目注意下 double 精度问题就可以过了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/415
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

最小树形图 / 朱刘算法
前置定义 树形图:在一个有向图中,满足存在一个入度为 $0$ 的点,除了该点入读均为 $1$,且该图不存在环,那么称为树形图。 最小树形图:给定有向边权图,求以某点为根的边权和最小的子…
扫描二维码继续阅读
2019-01-20
标签
近期评论