BZOJ 2260 商店购物/BZOJ 4349 最小树形图


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2260

                 http://www.lydsy.com/JudgeOnline/problem.php?id=4349

题意:要买一些东西一些次数,有一些优惠条件,即只要买过 a 物品则 b 物品都可以以某个优惠价购买,求最小费用....


每个需要买的物品至少买一次后就都能以优惠价购买了,显然这么做一定是最优的... 那么就是裸的朱刘算法的问题了...

在此简要给出朱刘算法的流程... 详解有生之年系列....

朱刘算法是一个由中国人发明的用于求解最小树形图的算法,时间复杂度为\(O(nm)\)

流程如下:

  1. 找出除根节点外每个点的最小入边,置入边集 E,记为 mn[]
  2. 判断原图在只通过边集 E 下是否有除根节点以外的独立点,若有,算法无解
  3. 判断是否有环,若无,则得到的边集 E 即原图的最小树形图,贪心的证明是显然的...
  4. 若有环,则记录环的编号后对环进行缩点,对于环之间的边,重建方式为:对于环中点 x,若有边 x->i val 则连接 new->i val,若有边 i->x val 则连接 i->new val-mn[x]
  5. 置新点数为环数,继续循环

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2260 商店购物/BZOJ 4349 最小树形图


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,