题目链接: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. 置新点数为环数,继续循环

upd 2018/05/16:这里发现找最小入边的过程可以用可并堆优化复杂度到 \(O(n^2log_n)\),或者进一步使用斐波那契堆就是 O\(n^2\) 的了。

 


一个非常弱的准退役OIER